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

[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.

[uvasarker]

Hi boss,
Now, it's WA. Please, help me. Give me some critical test cases. Here is my code:

Code: Select all

/* removed */


[brianfry713]

Try input 3 3, the output should be 1.

[uvasarker]

Thanks a lot boss I got it AC

[@li_kuet]

Try this Input :

Code: Select all

3
5 5
5 7
1 1000000

Output should be :

Code: Select all

1
2
30123


[shuvokr]

Need help.. Got TLE again and again but why ???

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

#define sf scanf
#define pf printf
#define LLU unsigned long long
#define Lu unsigned long
#define LLD long long
#define LD long
int N = 1000000;
bool *status = new bool[1000000], *res = new bool[1000000];
int main()
{
    int sqrtn, i, j;
    for(i = 0; i <= N; i++) status[i] = true;
    for(i = 4; i <= N; i += 2) status[i] = false;
    status[2] = true;

    for(i = 3; i <= 1000; i += 2)
        if(status[i])
            for(j = i * i; j <= N; j += i)
                status[j] = false;

    for(i = 1; i <= N; i++) res[i] = false;

    for(i = 3; i <= N; i += 2)
        if(status[i])
        {
            int sk = i;
            int sum = 0;
            int len = (int)(log10(sk));
            for(int k = 0; k <= len; k++)
            {
                sum += sk % 10;
                sk = sk / 10;
            }
            if(status[sum]) res[i] = true;
        }
    res[2] = true;
    int m, n, T;
    sf("%d", &T);
    while(T--)
    {
        int cou = 0;
        sf("%d%d", &m, &n);
        if(m <= 2) cou = 1;
        if(m % 2 == 0) m = m + 1;
        for(i = m; i <= n; i = i + 2)
            if(res[i]) cou++;
        pf("%d\n", cou);
    }
    return 0;
}


[brianfry713]

From uhunt:
kannabyz> pre calculate number of digit primes from 1 to 1000000 , when you get t1 & t2 , number of digit primes t2 subtract number of digit primes t1
kannabyz> if t1 = 10, t2 = 100 . Number of digit primes at 10 is 4 and number of digit primes at 100 is 14
kannabyz> 100 - 10 = 14 - 4 = 10