10533 - Digit Primes

[Zhou Yiyan@SHU]

That's right. Repeatedly prime test would be a much more time consuming stuff. Avoid this would save a lot of time.

[oulongbin]

this is my code.
i think it is right.can someone tell me why i always gei WA
[cpp]
#include <iostream>
using namespace std;
#include <cstdio>

int b[1000000]={0};
void prime()
{
int i,j;
b[0]=1;
b[1]=1;
for(i=1;i<1000;i++)
if (b[i]==0)
for(j=2;j<=1000000/i;j++)
b[i*j]=1;
}


int main()
{
prime();
long i;
int dp[1000000]={0};
int df[1000000]={0};
int dcnt=0;

long temp;
long t;
for(i=0;i<1000000;i++)
{
if(b[i]==1)
dp[i]=dcnt;
else
{
t=i;
temp=t%10;
t/=10;
while(t!=0)
{
temp+=t%10;
t/=10;
}
if(b[temp]==0)
{
dp[i]=++dcnt;
df[i]=1;
}
else
dp[i]=dcnt;
}

}

int n;
cin>>n;
long u,v,ch;
while(n--)
{
cin>>u>>v;
if(u>v)
{
ch=u;
u=v;
v=ch;
}
if(df[u]==1&&df[v]==1)
cout<<dp[v]-dp[u]+1<<endl;
else if((df[u]==1&&df[v]!=1)||(df[u]!=1&&df[v]==1))
cout<<dp[v]-dp[u]+1<<endl;
else
cout<<dp[v]-dp[u]<<endl;
}
return 0;
}
[/cpp]

[oulongbin]

please help me,i dont know why!!
[cpp]
removed after AC.
[/cpp]

[wanderley2k]

please help me,i dont know why!!
[cpp]

if(t1==t2&&a[t1]==1)
cout<<"1"<<endl;
else if(t1==t2&&a[t1]==0)
cout<<"0"<<endl;
else if((a[t1]==1&&a[t2]==0)||(a[t1]==0&&a[t2]==1)||(a[t1]==1&&a[t2]==1))
cout<<c[t2]-c[t1]+1<<endl;
else
cout<<c[t2]-c[t1]<<endl;
[/cpp]

Try this only in your output

[cpp]
cout<<c[t2]-c[t1-1]<<endl;
[/cpp]

I thinks it is the better form to make output I got a lot of Wrong because this too!

Wanderley

[oulongbin]

thank you very much!
i got AC on your opinion,thanx!!

[Ali Arman Tamal]

I am getting WA from the judge . But all the samples I've tried home are correct. Please help if you can.

I will really appreciate some test cases.

Here is my code:

Code: Select all


CUT AFTER AC



I've tried a lot and still WA. Please help !

[Ali Arman Tamal]

Nevermind. I got ACC at last . I made a mistake in the output statement.

Here are some test cases :

INPUT :

12
1 999999
1 1
1 10
9 12
240320 240350
3 20
204525 505639
200 300
1000 3000
2056 31256
999984 999999
999985 999985


OUTPUT:

30123
0
4
1
0
4
9096
8
133
1364
0
0

HAVE A NICE DAY !

[Fuad Hassan_IIUC(DC)]

PLZ help me out. I am getting TLE.Advance thanks 2 the helpers.

#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define max 1000009
long seive[max];
void genseive()
{
int i,j;
int sq=sqrt(max);
seive[0]=seive[1]=1;
for(i=2;i<=sq;i++)
{
for(j=i+i;j<max;j+=i)
seive[j]=1;
}

}

int main()
{
genseive();
long input,d,e,i,j,k,counter,len,sum;
char l[1000009];
scanf("%ld",&input);
for(i=0;i<input;i++)
{
counter=0;
scanf("%ld %ld",&d,&e);
for(j=d;j<=e;j++)
{
if(seive[j]==0)
{
sprintf(l,"%d",j);
len=strlen(l);
sum=0;
for(k=0;k<len;k++)
sum+=l[k]-48;
if(seive[sum]==0)
counter++;
}
else continue;
}
printf("%ld",counter);
printf("\n");
}
return 0;
}

[Martin Macko]

scanf("%ld %ld",&d,&e);
for(j=d;j<=e;j++)
{
...
}

There maight be as many as 500000 test cases in the input and in any of them you may have t2=1000000. Just iterating through all numbers will not fit in the time limit. Try to find a more sophisticated solution.

[tosun_ewu]

Thanks got AC.

[helloneo]

you need to check the input number and the digit sum of the number both are prime..

Code: Select all

                if (is_prime[i] && is_prime[sum])
                        dp[i] = dp[i-1] + 1;
                else
                        dp[i] = dp[i-1];


[boshkash1986]

i am not clear about a certain input which is

3 20
as your output is 4 while mine is 3 and when i traced it i found that it is three
from 3 to 20 inclusive (i.e. ignoring the limits) here are the prime numbers and digits

5,7,11
only which ae three only
i am consfused can you help me

[Ali Arman Tamal]

primes between t1 and t2 (inclusive).

3 is also digit prime in 3 - 20

it will be 4 'cause - 3 , 5 , 7 , 11 ,

the term inclusive is applied to both t1 and t2 , not only t2

Get it ?

Good luck!

[deena sultana]

dear friends,
i m getting tle again and again for 10533.

what i did, the summary is here.
1. first i find all the prime numbers using sieve alg.
2.for each prime number i checked if it is digit prime.
3.i used a bool array digitPr[1000002] to keep track the digit prime.
4. if the number n is digit prime then digitPr[n]=1 else 0
5. then i take the input t1 and t2
6. and count the 1s of the digitPr array within this range.

thats all. Any suggestion plz?
Plz help me to speedup my program..

[emotional blind]

Your all steps are great except step 6,
count is costly,
you have to do some dp
before starting taking input
better you manage another array,

such as NumberOfPrime[max],
and in NumberOfPrime[i] store number of primes in between 0 and i
do it using your bool array
and then take input

and output must be NumberOfPrime[t2]-NumberOfPrime[t1-1],
its less costly