## 10533 - Digit Primes

Moderator: Board moderators

### hi hamedv

i think its not needed to close the bracket as you have said. It works the same as you think.

No venture no gain

with best regards
------------------------
ishtiaq ahmed
ishtiaq ahmed
Learning poster

Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

mr ishtiaqq,

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)

it will work good as you want.

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am

### WA-10533(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

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++;
}
}
else
}
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)
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
ishtiaq ahmed
Learning poster

Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### post reply of previous submission of 10533

Jan bhia was written
Code: Select all

Let there are 10 data in the array as follows
Code: Select all

1  2  3  4  5  6  7  8  9  10
|  |  |  |  |  |  |  |  |  |
N  P  P  N  P  N  P  N  N  N

here
Code: Select all

N-> Not prime
P-> Prime & have prime digit

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

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

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
Question: Find the total answer from 5th[a] element to 10th[b] element?

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

Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

### Re: 10533 - Digit Primes

Someone can plesae tell me why I'm getting TLE ?
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[a-1]<<endl;
}
return 0;
}

mukit
New poster

Posts: 48
Joined: Wed Nov 21, 2007 10:09 am

### Re: 10533 - Digit Primes

probably your is_dp function is costly. try to re-implement this is_dp using something real dp
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;
}
}
}
}

emotional blind
A great helper

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

### 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 :
Code: Select all
Removed after AC

Last edited by mukit on Mon May 19, 2008 3:27 pm, edited 1 time in total.
mukit
New poster

Posts: 48
Joined: Wed Nov 21, 2007 10:09 am

### Re: 10533 - Digit Primes

now, try again with replacing all cin-cout with scanf-printf.

emotional blind
A great helper

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

### 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 cin-cout getting TLE?

After all thank you very much.
mukit
New poster

Posts: 48
Joined: Wed Nov 21, 2007 10:09 am

### Re: 10533 - Digit Primes

mukit wrote:Thank's a lot emotional blind. I got AC with 0.56 sec.

You are welcome.
mukit wrote: It didn't find the memset() function in ANSI C with header #include<stdio.h>

#include <string.h>

mukit wrote: Another thing why it took such a huge time(3.00) with cin-cout getting TLE?

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.

emotional blind
A great helper

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

### 10533 - Digit Primes

Ishtiaq Ahmed wrote:
Jan bhia was written

Edit!!!!!!
Last edited by lnr on Wed Jul 02, 2008 2:07 pm, edited 1 time in total.

lnr
Experienced poster

Posts: 134
Joined: Sat Jun 30, 2007 2:52 pm

### 10533 - Digit Primes

emotional blind wrote:
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.

Why cin and cout are costly?
How to use it.

lnr
Experienced poster

Posts: 134
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 10533 - Digit Primes

PLZZ Help...I am Getting TLE in this problem
I used sieve for prime & dprime.Current sieve takes around 0.2-0.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");
}
shekhar
New poster

Posts: 6
Joined: Wed Jul 09, 2008 12:34 pm

### 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.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am