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