10533  Digit Primes
Moderator: Board moderators

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

 New poster
 Posts: 28
 Joined: Mon Mar 01, 2004 11:29 pm
Re: 10533 WA
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[t11]<<endl;
[/cpp]
I thinks it is the better form to make output I got a lot of Wrong because this too!
Wanderley
 Ali Arman Tamal
 Learning poster
 Posts: 76
 Joined: Sat Jan 15, 2005 5:04 pm
 Location: Dhaka
 Contact:
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:
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
 Ali Arman Tamal
 Learning poster
 Posts: 76
 Joined: Sat Jan 15, 2005 5:04 pm
 Location: Dhaka
 Contact:

 New poster
 Posts: 18
 Joined: Fri Jan 07, 2005 9:35 pm
 Location: Bangladesh
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;
}
#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

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: 10533TLE!!
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++)
{
...
}
..
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[i1] + 1;
else
dp[i] = dp[i1];

 New poster
 Posts: 21
 Joined: Tue Jan 10, 2006 12:25 am
 Ali Arman Tamal
 Learning poster
 Posts: 76
 Joined: Sat Jan 15, 2005 5:04 pm
 Location: Dhaka
 Contact:

 New poster
 Posts: 36
 Joined: Mon Jun 19, 2006 5:43 pm
 Location: Bangladesh
 Contact:
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..
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..

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
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[t11],
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 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[t11],
its less costly