10533  Digit Primes
Moderator: Board moderators

 Learning poster
 Posts: 53
 Joined: Sat Jul 29, 2006 7:33 am
 Location: (CSE,DU), Dhaka,Bangladesh
hi hamedv
i think its not needed to close the bracket as you have said. It works the same as you think.
Thank you for your reply.
Thank you for your reply.
No venture no gain
with best regards

ishtiaq ahmed
with best regards

ishtiaq ahmed
 newton
 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
mr ishtiaqq,
you needn't count upto i<SIZE for the outer loop.
if you replaced:
it will work good as you want.
you needn't count upto i<SIZE for the outer loop.
if you replaced:
Code: Select all
the condition i<SIZE
into:
i<= sqrt(SIZE)

 Learning poster
 Posts: 53
 Joined: Sat Jul 29, 2006 7:33 am
 Location: (CSE,DU), Dhaka,Bangladesh
WA10533(prime digit)
I have updated my code as follows. Firstly it faced TLE and then as follows. Please try to help me.
Code: Select all
#include<stdio.h>
#include<math.h>
#define SIZE 1000001
long a,b,data[SIZE]={0},add[SIZE]={0};
void s (void);
long sum_prime(void);
int main()
{
long k,i,result,cas,sum=0,z,dum,m;
s();
sum=0;
for(i=0;i<SIZE;i++)
{
if(!data[i])
{
z=i;dum=0;
while(z)
{
m=z%10;
dum +=m;
z /=10;
}
if(!data[dum])
{
sum++;
add[i]=sum;
}
}
else
add[i]=sum;
}
scanf("%ld",&cas);
for(k=1;k<=cas;k++)
{
scanf("%ld %ld",&a, &b);
result=sum_prime();
printf("%ld\n",result);
}
return 0;
}
void s(void)
{
long i,j,sqrtNum;
data[0]=1;
data[1]=1;
for(i=4;i<SIZE;i+=2)
data[i]=1;
sqrtNum = (long)sqrt(SIZE);
for(i=3;i<sqrtNum;i+=2)
for(j=i;i*j<SIZE;j++)
if(!data[i*j])
data[i*j]=1;
}
long sum_prime(void)
{
long XX,z,dum,m;
if(a!=b)
XX=add[b]add[a];
else if(a==b)
{
if(!data[a])
{
dum=0;z=a;
while(z)
{
m=z%10;
dum +=m;
z /=10;
}
if(!data[dum])
XX=1;
}
else
XX=0;
}
return XX;
}
No venture no gain
with best regards

ishtiaq ahmed
with best regards

ishtiaq ahmed

 Learning poster
 Posts: 53
 Joined: Sat Jul 29, 2006 7:33 am
 Location: (CSE,DU), Dhaka,Bangladesh
post reply of previous submission of 10533
Jan bhia was written
Let there are 10 data in the array as follows
here
Now i consider that if data is prime and the prime data's summation of didits are prime then i add them just like these
Now when i am asked to find out the total summation that is asked by this problem tryed to solve like this:
Code: Select all
What if you use add[b]  add[a1] ?
Code: Select all
1 2 3 4 5 6 7 8 9 10
         
N P P N P N P N N N
Code: Select all
N> Not prime
P> Prime & have prime digit
Code: Select all
1 2 3 4 5 6 7 8 9 10
         
N P P N P N P N N N
add[]>0 1 2 2 3 3 4 4 4 4
Code: Select all
Question: Find the total answer from 5th[a] element to 10th[b] element?
answer: add[b1]  add[a1] that is
add[9]  add[4]
Code: Select all
Question: Find the total answer from 4th[a] element to 4th[b] element?
answer: First i have checked if the 4th element is prime and have prime digit then i printed 1 otherwise 0;
No venture no gain
with best regards

ishtiaq ahmed
with best regards

ishtiaq ahmed
Re: 10533  Digit Primes
Someone can plesae tell me why I'm getting TLE ?
I read previous posts.
Here is my code :
Thank's in advance.
I read previous posts.
Here is my code :
Code: Select all
#include<iostream>
#include<cstdio>
using namespace std;
#define SIZE 1000002
long a,b,i,j;
char data[SIZE]={0};
int dp[SIZE];
int nop[SIZE];
void sieve(void)
{
int i, j, k;
data[0] = 1;
data[1] = 1;
for (i=4; i<SIZE; i+=2)
{
data[i] = 1;
}
for (i=3; i<SIZE; i+=2)
{
if (!data[i])
{
k = SIZE / i;
for (j=i; j<=k; j+=2)
{
data[i * j] = 1;
}
}
}
}
void is_dp()
{
long x,z,ct=0,du,m=0;
for(i=0;i<SIZE;i++)
{
if(!data[i])
{
z=x=i;
du=0;
while(z)
{
m=z%10;
du+=m;
z/=10;
}
if(!data[du])
{
dp[i]=1;
}
}
}
}
void sum_prime()
{
int sum=0,dum,m=0,z;
for(i=0;i<=SIZE;i++)
{
if(dp[i])
{
sum+=1;
}
nop[i]=sum;
}
}
int main()
{
long test;
sieve();
is_dp();
sum_prime();
cin >> test;
for(long i=0;i<test;i++)
{
cin>>a>>b;
cout<<nop[b]nop[a1]<<endl;
}
return 0;
}
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Re: 10533  Digit Primes
probably your is_dp function is costly. try to reimplement this is_dp using something real dp
Something like this 
Something like this 
Code: Select all
int ds[SIZE];
int dsum(int n){
int &ret = ds[n];
if(1!=ret)return ret;
if(n<10)return ret=n;
return ret = n%10 + dsum(n/10);
}
void is_dp(){
long x,z,ct=0,du,m=0;
memset(ds,1,sizeof(ds));
for(i=0;i<SIZE;i++)
{
if(!data[i])
{
du = dsum(i);
if(!data[du])
{
dp[i]=1;
}
}
}
}
Re: 10533  Digit Primes
To emotional Blind,
I did as you said but got TLE again with running time 3.00 sec like past.
I did it as :
Thanks for reply.
I did as you said but got TLE again with running time 3.00 sec like past.
I did it as :
Code: Select all
Removed after AC
Last edited by mukit on Mon May 19, 2008 3:27 pm, edited 1 time in total.
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Re: 10533  Digit Primes
now, try again with replacing all cincout with scanfprintf.
Re: 10533  Digit Primes
Thank's a lot emotional blind. I got AC with 0.56 sec.
But something was ambiguous to me. It didn't find the memset() function in ANSI C with header #include<stdio.h> and
only #include<cstdio> header in C++. I had to use #include<iostream> with namespace.
Another thing why it took such a huge time(3.00) with cincout getting TLE?
After all thank you very much.
But something was ambiguous to me. It didn't find the memset() function in ANSI C with header #include<stdio.h> and
only #include<cstdio> header in C++. I had to use #include<iostream> with namespace.
Another thing why it took such a huge time(3.00) with cincout getting TLE?
After all thank you very much.
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Re: 10533  Digit Primes
You are welcome.mukit wrote:Thank's a lot emotional blind. I got AC with 0.56 sec.
#include <string.h>mukit wrote: It didn't find the memset() function in ANSI C with header #include<stdio.h>
cin and cout is lot more costly than scanf and printf, this is noticeable for the problems which needs large input and output data to handle.mukit wrote: Another thing why it took such a huge time(3.00) with cincout getting TLE?
I think it takes more than 3.00 seconds. though 3.00 is the time limit, after 3.00 seconds the judge system terminates your program.
10533  Digit Primes
Ishtiaq Ahmed wrote:
Edit!!!!!!Jan bhia was written
Last edited by lnr on Wed Jul 02, 2008 2:07 pm, edited 1 time in total.
10533  Digit Primes
emotional blind wrote:
Would someone please tell about the use of memset()?
Why cin and cout are costly?cin and cout is lot more costly than scanf and printf, this is noticeable for the problems which needs large input and output data to handle.
I think it takes more than 3.00 seconds. though 3.00 is the time limit, after 3.00 seconds the judge system terminates your program.
Would someone please tell about the use of memset()?
 The header file.
How to use it.
Re: 10533  Digit Primes
PLZZ Help...I am Getting TLE in this problem
I used sieve for prime & dprime.Current sieve takes around 0.20.3 seconds for calculation.Can anyone help me out...how optimization can be done??
Here is my code...
I used sieve for prime & dprime.Current sieve takes around 0.20.3 seconds for calculation.Can anyone help me out...how optimization can be done??
Here is my code...
Code: Select all
#include<iostream>
#include<cmath>
using namespace std;
bool prime[1000001];
bool dprime[1000001];
void seive()
{
int m=1000;
memset(prime,true,sizeof(prime));
prime[0]=false;
prime[1]=false;
for(int i=2;i<=m;i++)
if(prime[i])
for(int k=i*i;k<=1000000;k+=i)
prime[k]=false;
memset(dprime,false,sizeof(dprime));
dprime[0]=false;
dprime[1]=false;
for(int j=2;j<=1000000;j++)
{
int sum=0,num=j;
while(num>=1)
{
sum+=num%10;
num=num/10;
}
if(prime[sum])
dprime[j]=true;
}
}
int main()
{
int test,a,b;
seive();
scanf("%d",&test);
while(test)
{
scanf("%d %d",&a,&b);
int n,count=0;
for(n=a;n<=b;n++)
{
if(prime[n] && dprime[n])
count++;
}
printf("%d\n",count);
}
system("pause");
}
Re: 10533  Digit Primes
Some one please help me to get Acc less TLE. I tried but failed so many times.
Code: Select all
removed
Last edited by Obaida on Tue Aug 05, 2008 6:49 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.