Posted:

**Sun Jul 18, 2004 12:54 pm**That's right. Repeatedly prime test would be a much more time consuming stuff. Avoid this would save a lot of time.

Page **3** of **8**

Posted: **Sun Jul 18, 2004 12:54 pm**

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

Posted: **Sun Aug 15, 2004 3:42 pm**

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*==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*==1)*

dp*=dcnt;*

else

{

t=i;

temp=t%10;

t/=10;

while(t!=0)

{

temp+=t%10;

t/=10;

}

if(b[temp]==0)

{

dp*=++dcnt;*

df*=1;*

}

else

dp*=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==1&&df[v]==1)

cout<<dp[v]-dp+1<<endl;

else if((df==1&&df[v]!=1)||(df!=1&&df[v]==1))

cout<<dp[v]-dp+1<<endl;

else

cout<<dp[v]-dp<<endl;

}

return 0;

}

[/cpp]

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

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

dp

else

{

t=i;

temp=t%10;

t/=10;

while(t!=0)

{

temp+=t%10;

t/=10;

}

if(b[temp]==0)

{

dp

df

}

else

dp

}

}

int n;

cin>>n;

long u,v,ch;

while(n--)

{

cin>>u>>v;

if(u>v)

{

ch=u;

u=v;

v=ch;

}

if(df==1&&df[v]==1)

cout<<dp[v]-dp+1<<endl;

else if((df==1&&df[v]!=1)||(df!=1&&df[v]==1))

cout<<dp[v]-dp+1<<endl;

else

cout<<dp[v]-dp<<endl;

}

return 0;

}

[/cpp]

Posted: **Sun Sep 05, 2004 2:47 pm**

please help me,i dont know why!!

[cpp]

removed after AC.

[/cpp]

[cpp]

removed after AC.

[/cpp]

Posted: **Wed Sep 15, 2004 9:59 pm**

Try this only in your outputoulongbin wrote: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]

[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

Posted: **Sat Sep 18, 2004 3:46 pm**

thank you very much!

i got AC on your opinion,thanx!!

i got AC on your opinion,thanx!!

Posted: **Sat Feb 05, 2005 4:52 pm**

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:
I've tried a lot and still WA. Please help !

I will really appreciate some test cases.

Here is my code:

Code: Select all

```
CUT AFTER AC
```

Posted: **Sun Feb 06, 2005 5:28 am**

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 !

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 !

Posted: **Thu Sep 22, 2005 3:24 pm**

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;

}

#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;

}

Posted: **Fri Sep 23, 2005 3:49 am**

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.Fuad Hassan_IIUC(DC) wrote: scanf("%ld %ld",&d,&e);

for(j=d;j<=e;j++)

{

...

}

Posted: **Sat Nov 19, 2005 10:27 am**

Thanks got AC.

Posted: **Sat Nov 19, 2005 12:00 pm**

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];
```

Posted: **Wed Feb 01, 2006 12:21 pm**

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

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

Posted: **Wed Feb 01, 2006 3:23 pm**

3 is also digit prime in 3 - 20primes between t1 and t2 (inclusive).

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

Get it ?

Good luck!

Posted: **Wed Jun 28, 2006 5:21 pm**

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

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

Posted: **Wed Jun 28, 2006 5:33 pm**

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

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

do it using your bool array

and then take input

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

its less costly