## 10533 - Digit Primes

All about problems in Volume CV. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

That's right. Repeatedly prime test would be a much more time consuming stuff. Avoid this would save a lot of time.
Zhou Yiyan@SHU
New poster

Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China

### 10533 WA

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
Learning poster

Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 10533 WA

please help me,i dont know why!!
[cpp]
removed after AC.
[/cpp]
Last edited by oulongbin on Sat Sep 18, 2004 3:48 pm, edited 1 time in total.
oulongbin
Learning poster

Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### Re: 10533 WA

oulongbin 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]

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

Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

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

Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 10533 WA

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
Learning poster

Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka

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 !

Ali Arman Tamal
Learning poster

Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka

### 10533TLE!!

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;
}
fuad
Fuad Hassan_IIUC(DC)
New poster

Posts: 18
Joined: Fri Jan 07, 2005 9:35 pm
Location: Bangladesh

### Re: 10533TLE!!

Fuad Hassan_IIUC(DC) wrote: 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.

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### 10533

Thanks got AC.
Last edited by tosun_ewu on Wed Jan 25, 2006 2:24 pm, edited 1 time in total.
tosun_ewu
New poster

Posts: 4
Joined: Tue Aug 03, 2004 7:02 am

### ..

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

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

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

Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

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!

Ali Arman Tamal
Learning poster

Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka

### 10533, TLE & TLE &.....

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..
deena sultana
New poster

Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh

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

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh

PreviousNext

Return to Volume CV

### Who is online

Users browsing this forum: No registered users and 1 guest