10533 - Digit Primes

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Nishith csedu 1448
New poster
Posts: 4
Joined: Fri May 23, 2008 6:55 am
Location: Dhaka
Contact:

Re: 10533 - Digit Primes

Post by Nishith csedu 1448 » Fri Aug 01, 2008 9:11 pm

Your code takes so many times when the input is 1 999999.
You should use faster and most efficient sieve for this problem.
Just think about it." The sum of the digits of a prime number is prime or not''- it can be checked very simply,think about those primes.
Best of luck !!!!!!!!!!!!!!
Sopno dhaka mon akash choar.............

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10533 - Digit Primes

Post by Obaida » Tue Aug 05, 2008 6:54 am

Thanks Nishith you helped me a lot!!! :D
try_try_try_try_&&&_try@try.com
This may be the address of success.

GUC.HassanMohamed
New poster
Posts: 3
Joined: Fri Aug 22, 2008 5:22 pm

Re: 10533 - Digit Primes

Post by GUC.HassanMohamed » Fri Aug 22, 2008 5:36 pm

Hello everyone,

I have already solved this problem using DP and implemented it in C++ and got accepted in 0.9 secs.

However I can't pass this problem using Java and same algorithm for C++ implementation.

Any help would be appreciated.

Thanks in advance.

Code: Select all

import java.io.*;
import java.util.*;

public class DigitPrimes {
	static boolean [] a=new boolean [1000001];
        static int [] dp = new int [1000001];
	public static void main(String[] args) throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader (isr);
		int times = new Integer(br.readLine());
		getPrime(a);
		for(int i = 0 ; i < times ;i++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			int t1 = new Integer(st.nextToken()) , t2 = new Integer(st.nextToken());
			int ret = calcDP(t2)-calcDP(t1-1>0?t1-1:0);
		        System.out.println(ret);
                  }
	}
	public static int sum(int num){
		int sum = 0;
		while(num > 0){
			sum += num%10;
			num /= 10;
		}
		return sum;
	}
	public static void getPrime(boolean [] a)
	{
		Arrays.fill(a,true);
		a[0]=a[1]=false;
		for(int i=2;i*i<a.length;i++)
		{
			if(a[i])
			{
					for(int j=i*i;j<a.length;j+=i)
				     a[j]=false;
			}
		}
	}
	public static int calcDP(int i){
		if(dp [i] != 0)return dp[i];
		for(int j = 1;j <= i;j++){
			dp [j] = dp[j-1];
			if(a[j] && a[sum(j)])
				dp[j] = dp [j - 1] + 1;
			}
		return dp[i];
	}
}

dipal
New poster
Posts: 4
Joined: Mon Apr 27, 2009 9:23 am
Location: BUET

10533 - Digit Primes

Post by dipal » Thu May 14, 2009 11:25 am

i am not understanding what is problem with me.
im finding all output correct using my algo.

but why i am finding Wa. ??

Code: Select all

#include <stdio.h>
bool data[1000100]={0};
long long dt[1000100]={0},i,j,n,m,count,max=0,num,num2;
long long test;
int main()
{
    for (i=2; i<=1000; )
    {
        for (j=2*i; j<=1000000; j+=i) data[j]=1;
        for (i++; data[i]; i++);
    }
    data[0]=data[1]=1;
    max=0;
    scanf("%lld",&test);
    while (test--)
    {
        scanf("%lld%lld",&n,&m);
        count=0;
        if (m>max)
        {
            for (i=max; i<=m; i++)
            {
                if (data[i])
                {
                    dt[i]=dt[max]+count;
                    continue;
                }
                num=i;
                num2=0;
                while (num)
                {
                    num2+=num%10;
                    num/=10;
                }                
                if (!data[num2]) count++;
                dt[i]=dt[max]+count;
            }
            max=m;
        }
        printf("%lld\n",dt[m]-dt[n-1]);
    }
    return 0;
}

Please somebody explain (used data as Prime Table (0 is prime) (1 is not prime));
thanx

sms.islam
New poster
Posts: 19
Joined: Sat Oct 10, 2009 10:28 am

Re: 10533 - Digit Primes

Post by sms.islam » Tue Nov 10, 2009 5:42 pm

i am getting TLE for this problem.

i use this function to check prime number.
[c]

long prime_count(long x)
{
long i;
if(x==1) return 0;
else if(x==2) return 1;
else if(x%2==0) return 0;

for ( i = 3 ; i*i <= x ; i+=2)
{
if(x%i==0)
return 0;
}
return 1;
}
[c]

to count the sum of prime number digit i use this function
[c]
long digit_count(long x)
{
long sum=0;
while(x>0)
{
sum=sum+x%10;
x=x/10;
}
return sum;
}
[c]

is there anything wrong?
please help me.
thanx

masum.shafayat
New poster
Posts: 3
Joined: Wed Nov 11, 2009 1:09 pm

Re: 10533 - Digit Primes

Post by masum.shafayat » Mon Dec 21, 2009 10:25 am

Code: Select all

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
	bool prime[1000000];
	long i,j;
	for(i=2;i<=1000000;i++)
		prime[i]=true;
	prime[0]=false;
	prime[1]=false;
	for(i=2;i<=1000000;i++)
	{
		
		for(j=i*2;j<=1000000;j=j+i)
		{
			if(prime[j])
				prime[j]=false;
		}
	}
	long cas;
	cin>>cas;
	while(cas--)
	{
		long t1,t2;
		cin>>t1>>t2;
		long sum=0,c=0;
		long n,v=0;
		for(i=t1;i<=t2;i++)
		{
			if(i<=1000000)
			{
				if(prime[i])
				{
					n=i;
				}
			}
			sum=0;
			if(n>0)
			{
				while(n!=0)
				{
					sum=sum+n%10;
					n=n/10;
				}
				if(prime[sum])
					c++;
			}
		}
		cout<<c<<endl;
		c=0;
	}


	return 0;
}

Some one help me plz. I got TLE by this.

chris benoit
New poster
Posts: 1
Joined: Wed Dec 29, 2010 9:46 am

Re: 10533 - Digit Primes

Post by chris benoit » Wed Dec 29, 2010 10:10 am

I code this and got time limit exeed
can anyone help me......

Code: Select all

#include <stdio.h>

int main(){
    long int n,t1,t2,i,a;
    scanf("%ld",&n);
    for(i=1;i<=n;i++){
        scanf("%ld%ld",&t1,&t2);
        long int k=0;
        for(;t1<=t2;t1++){
            for(a=2;a<=t1;a++){
                 if(a==t1)
                     break;
                 if(t1%a==0)
                     break;
            }
	    if(a==t1){

	    long int j=t1;
	    int total=0,p;
	    while(j!=0){
		p=j%10;
		j=j/10;
		total=total+p;
	    }
	    for(a=2;a<=total;a++){
		 if(a==total){
		     k++;
		     break;
		 }
		 if(total%a==0)
		     break;
	    }}
	}
	printf("%ld\n",k);
    }
    return 0;
}
 

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 10533 - Digit Primes

Post by helloneo » Fri Dec 31, 2010 3:15 pm

See some previous posts..
There are answers for the TLE issue

AlexWolfen
New poster
Posts: 1
Joined: Tue Jan 25, 2011 5:34 pm
Location: United States
Contact:

Online Casino

Post by AlexWolfen » Tue Jan 25, 2011 5:35 pm

Mike are you there?

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10533 - Digit Primes

Post by plamplam » Sun Aug 07, 2011 1:48 pm

Here are two input sets which helped me solve this problem.

Set 1:

Code: Select all

11
1 10
1 1000000
1 100
2 7
1 6
2 8
4 10
4 9
4 11
4 100
5 133

Code: Select all

4
30123
14
4
3
4
2
2
3
12
15
Set 2:

Code: Select all

9
60917 90107
60917 90108
60917 90106
60916 90107
60918 90107
60916 90106
60918 90106
60918 90108
60916 90108

Code: Select all

925
925
924
925
924
924
923
924
925
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

10533 Digit Primes (TLE) why? please help me, please

Post by uvasarker » Sat Jan 07, 2012 12:37 pm

I use the sieve method to generates the all primes number in my code but also then the judge say TLE. Please help me. Here is my code.

Code: Select all

    #include<cstdio>
    #include<cstring>
    bool sieve[1000000];
             
    int main()
    {
        long i,j,t1,t2;
        sieve[0]=sieve[1]=0;
        for(i=2; i<1000000; i++) sieve[i]=1;
        for(i=2; i<1000000; i++)
        {
			if(sieve[i]!=0)
            {
				for(j=i+1; j<1000000; j++)
                {
					if (sieve[j]!=0)
                    {
						if((j%i)==0) sieve[j]=0;
                    }
                }
            }
        }
        long T;
        scanf("%ld",&T);
        
        while(T--)
        {
				scanf("%ld %ld",&t1,&t2);
				long prim=0;
				for(long I=t1 ; I<=t2 ; I++)
				{
						if(sieve[I]==1)
						{
								int sum=0,num=I,tmp;
								while(num!=0)
								{
										tmp=num%10;
										num=num/10;
										sum=sum+tmp;
								}
								if(sieve[sum]==1)
									prim++;
						}
				}
				printf("%ld\n",prim);	
        }
        return 0;
    }  


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by brianfry713 » Wed Jan 11, 2012 9:47 pm

Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by uvasarker » Sat Jan 28, 2012 10:40 am

I am still getting TLE. Please, help me. My updated code is here:

Code: Select all

#include<cstdio>
#include<cstring>
bool sieve[10001011]={0};

long rev( long I )
{
			long sum=0,num=I,tmp;
			while(num!=0)
			{
					tmp=num%10;
					num=num/10;
					sum=sum+tmp;
			}
		return sum;
}

int main()
{
        long t1,t2;
		long i,j;
		sieve[0]=1; sieve[1]=1;
		for(i=4 ; i<=1000000 ; i+=2) sieve[i]=1;
		for(i=3 ; i<=1000 ; i+=2)
		{
			if(sieve[i]==0)
			{
				for(j=i*i ; j<=10000008 ; j+=2*i)
				{
					sieve[j]=1;
				}
			}
		}
        long T;
        scanf("%ld",&T);
        
        while(T--)
        {
				scanf("%ld %ld",&t1,&t2);
				long prim=0;
				for(long I=t1 ; I<=t2 ; I++)
				{
						if(sieve[I]==0)
						{
								if(sieve[rev(I)]==0)
									prim++;
						}
				}
				printf("%ld\n",prim);	
        }
	return 0;
}  


uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by uvasarker » Sat Feb 11, 2012 9:24 am

Hi,
boss
I update more on this problem but still TLE.Please help me please, please, please, please, please.
Here is my code:

Code: Select all

#include<cstdio>
#include<cstring>
bool sieve[10001011]={0};
bool prim[1000000]={0};
long rev( long I )
{
			long sum=0,num=I;
			while(num!=0)
			{
					sum+=num%10;
					num=num/10;
			}
		return sum;
}

int main()
{
        long t1,t2;
		long i,j;
		prim[2]=1;
		sieve[0]=1; sieve[1]=1;
		for(i=3 ; i<=1000000 ; i+=2)
		{
			sieve[i+1]=1;
			if(sieve[i]==0 && i<=1000)
			{
				for(j=i*i ; j<=1000000 ; j+=2*i)
				{
					sieve[j]=1;
				}
			}
		}
		for(long I=3 ; I<=1000000 ; I+=2)
			{
					if(sieve[I]==0)
					{
							if(sieve[rev(I)]==0)
								prim[I]=1;
					}
			}

        long T;
        scanf("%ld",&T);
        
        while(T--)
        {
				scanf("%ld %ld",&t1,&t2);
				long pr=0,st;
				if(t1<=2 && t2>=2)
				{
						st=3;
						pr++;
				}
				else if(t1%2==0 && t1>=3)
				{
						st=t1+1;
				}
				else st=t1;
				for(long I=st ; I<=t2 ; I+=2)
				{
						if(prim[I]==1)
						{
								pr++;
						}
				}
				printf("%ld\n",pr);	
        }
	return 0;
}  


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by brianfry713 » Tue Feb 14, 2012 12:04 am

Precompute an array of size 1000000 that counts the number of digit primes up to that point. Your main I/O loop should just subtract the count of t1 from the count of t2.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 105 (10500-10599)”