10533 - Digit Primes

[Nishith csedu 1448]

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 !!!!!!!!!!!!!!

[Obaida]

Thanks Nishith you helped me a lot!!!

[GUC.HassanMohamed]

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]

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]

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]

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]

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]

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

[AlexWolfen]

Mike are you there?

[plamplam]

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

[uvasarker]

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]

Your Sieve method is too slow.
http://en.wikipedia.org/wiki/Sieve_of_E ... ementation

[uvasarker]

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]

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]

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.