## 10533 - Digit Primes

Moderator: Board moderators

### Re: 10533 - Digit Primes

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.............
Nishith csedu 1448
New poster

Posts: 4
Joined: Fri May 23, 2008 6:55 am
Location: Dhaka

### Re: 10533 - Digit Primes

Thanks Nishith you helped me a lot!!!
try_try_try_try_&&&_try@try.com
This may be the address of success.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10533 - Digit Primes

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.

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];   }}`
GUC.HassanMohamed
New poster

Posts: 3
Joined: Fri Aug 22, 2008 5:22 pm

### 10533 - Digit Primes

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
dipal
New poster

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

### Re: 10533 - Digit Primes

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?
thanx
sms.islam
New poster

Posts: 19
Joined: Sat Oct 10, 2009 10:28 am

### Re: 10533 - Digit Primes

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.
masum.shafayat
New poster

Posts: 3
Joined: Wed Nov 11, 2009 1:09 pm

### Re: 10533 - Digit Primes

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;} `
chris benoit
New poster

Posts: 1
Joined: Wed Dec 29, 2010 9:46 am

### Re: 10533 - Digit Primes

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

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

### Online Casino

Mike are you there?
AlexWolfen
New poster

Posts: 1
Joined: Tue Jan 25, 2011 5:34 pm
Location: United States

### Re: 10533 - Digit Primes

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

Set 1:
Code: Select all
`111 101 10000001 1002 71 62 84 104 94 114 1005 133`

Code: Select all
`430123144342231215`

Set 2:
Code: Select all
`960917 9010760917 9010860917 9010660916 9010760918 9010760916 9010660918 9010660918 9010860916 90108`

Code: Select all
`925925924925924924923924925`
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster

Posts: 151
Joined: Fri May 06, 2011 11:37 am

Previous