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
 Martin Macko
 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..
 emotional blind
 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