## 10533 - Digit Primes

Moderator: Board moderators

Nishith csedu 1448
New poster
Posts: 4
Joined: Fri May 23, 2008 6:55 am
Location: Dhaka
Contact:

### Re: 10533 - Digit Primes

Your code takes so many times when the input is 1 999999.
You should use faster and most efficient sieve for this problem.
Just think about it." The sum of the digits of a prime number is prime or not''- it can be checked very simply,think about those primes.
Best of luck !!!!!!!!!!!!!!
Sopno dhaka mon akash choar.............

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10533 - Digit Primes

Thanks Nishith you helped me a lot!!! try_try_try_try_&&&_try@try.com
This may be the address of success.

GUC.HassanMohamed
New poster
Posts: 3
Joined: Fri Aug 22, 2008 5:22 pm

### Re: 10533 - Digit Primes

Hello everyone,

I have already solved this problem using DP and implemented it in C++ and got accepted in 0.9 secs.

However I can't pass this problem using Java and same algorithm for C++ implementation.

Any help would be appreciated.

Code: Select all

``````import java.io.*;
import java.util.*;

public class DigitPrimes {
static boolean [] a=new boolean ;
static int [] dp = new int ;
public static void main(String[] args) throws IOException{
getPrime(a);
for(int i = 0 ; i < times ;i++){
int t1 = new Integer(st.nextToken()) , t2 = new Integer(st.nextToken());
int ret = calcDP(t2)-calcDP(t1-1>0?t1-1:0);
System.out.println(ret);
}
}
public static int sum(int num){
int sum = 0;
while(num > 0){
sum += num%10;
num /= 10;
}
return sum;
}
public static void getPrime(boolean [] a)
{
Arrays.fill(a,true);
a=a=false;
for(int i=2;i*i<a.length;i++)
{
if(a[i])
{
for(int j=i*i;j<a.length;j+=i)
a[j]=false;
}
}
}
public static int calcDP(int i){
if(dp [i] != 0)return dp[i];
for(int j = 1;j <= i;j++){
dp [j] = dp[j-1];
if(a[j] && a[sum(j)])
dp[j] = dp [j - 1] + 1;
}
return dp[i];
}
}
``````

dipal
New poster
Posts: 4
Joined: Mon Apr 27, 2009 9:23 am
Location: BUET

### 10533 - Digit Primes

i am not understanding what is problem with me.
im finding all output correct using my algo.

but why i am finding Wa. ??

Code: Select all

``````#include <stdio.h>
bool data={0};
long long dt={0},i,j,n,m,count,max=0,num,num2;
long long test;
int main()
{
for (i=2; i<=1000; )
{
for (j=2*i; j<=1000000; j+=i) data[j]=1;
for (i++; data[i]; i++);
}
data=data=1;
max=0;
scanf("%lld",&test);
while (test--)
{
scanf("%lld%lld",&n,&m);
count=0;
if (m>max)
{
for (i=max; i<=m; i++)
{
if (data[i])
{
dt[i]=dt[max]+count;
continue;
}
num=i;
num2=0;
while (num)
{
num2+=num%10;
num/=10;
}
if (!data[num2]) count++;
dt[i]=dt[max]+count;
}
max=m;
}
printf("%lld\n",dt[m]-dt[n-1]);
}
return 0;
}
``````

Please somebody explain (used data as Prime Table (0 is prime) (1 is not prime));
thanx

sms.islam
New poster
Posts: 19
Joined: Sat Oct 10, 2009 10:28 am

### Re: 10533 - Digit Primes

i am getting TLE for this problem.

i use this function to check prime number.
[c]

long prime_count(long x)
{
long i;
if(x==1) return 0;
else if(x==2) return 1;
else if(x%2==0) return 0;

for ( i = 3 ; i*i <= x ; i+=2)
{
if(x%i==0)
return 0;
}
return 1;
}
[c]

to count the sum of prime number digit i use this function
[c]
long digit_count(long x)
{
long sum=0;
while(x>0)
{
sum=sum+x%10;
x=x/10;
}
return sum;
}
[c]

is there anything wrong?
thanx

masum.shafayat
New poster
Posts: 3
Joined: Wed Nov 11, 2009 1:09 pm

### Re: 10533 - Digit Primes

Code: Select all

``````#include<iostream>
#include<math.h>
using namespace std;
int main()
{
bool prime;
long i,j;
for(i=2;i<=1000000;i++)
prime[i]=true;
prime=false;
prime=false;
for(i=2;i<=1000000;i++)
{

for(j=i*2;j<=1000000;j=j+i)
{
if(prime[j])
prime[j]=false;
}
}
long cas;
cin>>cas;
while(cas--)
{
long t1,t2;
cin>>t1>>t2;
long sum=0,c=0;
long n,v=0;
for(i=t1;i<=t2;i++)
{
if(i<=1000000)
{
if(prime[i])
{
n=i;
}
}
sum=0;
if(n>0)
{
while(n!=0)
{
sum=sum+n%10;
n=n/10;
}
if(prime[sum])
c++;
}
}
cout<<c<<endl;
c=0;
}

return 0;
}

``````
Some one help me plz. I got TLE by this.

chris benoit
New poster
Posts: 1
Joined: Wed Dec 29, 2010 9:46 am

### Re: 10533 - Digit Primes

I code this and got time limit exeed
can anyone help me......

Code: Select all

``````#include <stdio.h>

int main(){
long int n,t1,t2,i,a;
scanf("%ld",&n);
for(i=1;i<=n;i++){
scanf("%ld%ld",&t1,&t2);
long int k=0;
for(;t1<=t2;t1++){
for(a=2;a<=t1;a++){
if(a==t1)
break;
if(t1%a==0)
break;
}
if(a==t1){

long int j=t1;
int total=0,p;
while(j!=0){
p=j%10;
j=j/10;
total=total+p;
}
for(a=2;a<=total;a++){
if(a==total){
k++;
break;
}
if(total%a==0)
break;
}}
}
printf("%ld\n",k);
}
return 0;
}
``````

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

### Re: 10533 - Digit Primes

See some previous posts..
There are answers for the TLE issue

AlexWolfen
New poster
Posts: 1
Joined: Tue Jan 25, 2011 5:34 pm
Location: United States
Contact:

### Online Casino

Mike are you there?

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 10533 - Digit Primes

Here are two input sets which helped me solve this problem.

Set 1:

Code: Select all

``````11
1 10
1 1000000
1 100
2 7
1 6
2 8
4 10
4 9
4 11
4 100
5 133``````

Code: Select all

``````4
30123
14
4
3
4
2
2
3
12
15
``````
Set 2:

Code: Select all

``````9
60917 90107
60917 90108
60917 90106
60916 90107
60918 90107
60916 90106
60918 90106
60918 90108
60916 90108``````

Code: Select all

``````925
925
924
925
924
924
923
924
925
``````
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

I use the sieve method to generates the all primes number in my code but also then the judge say TLE. Please help me. Here is my code.

Code: Select all

``````    #include<cstdio>
#include<cstring>
bool sieve;

int main()
{
long i,j,t1,t2;
sieve=sieve=0;
for(i=2; i<1000000; i++) sieve[i]=1;
for(i=2; i<1000000; i++)
{
if(sieve[i]!=0)
{
for(j=i+1; j<1000000; j++)
{
if (sieve[j]!=0)
{
if((j%i)==0) sieve[j]=0;
}
}
}
}
long T;
scanf("%ld",&T);

while(T--)
{
scanf("%ld %ld",&t1,&t2);
long prim=0;
for(long I=t1 ; I<=t2 ; I++)
{
if(sieve[I]==1)
{
int sum=0,num=I,tmp;
while(num!=0)
{
tmp=num%10;
num=num/10;
sum=sum+tmp;
}
if(sieve[sum]==1)
prim++;
}
}
printf("%ld\n",prim);
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

I am still getting TLE. Please, help me. My updated code is here:

Code: Select all

``````#include<cstdio>
#include<cstring>
bool sieve={0};

long rev( long I )
{
long sum=0,num=I,tmp;
while(num!=0)
{
tmp=num%10;
num=num/10;
sum=sum+tmp;
}
return sum;
}

int main()
{
long t1,t2;
long i,j;
sieve=1; sieve=1;
for(i=4 ; i<=1000000 ; i+=2) sieve[i]=1;
for(i=3 ; i<=1000 ; i+=2)
{
if(sieve[i]==0)
{
for(j=i*i ; j<=10000008 ; j+=2*i)
{
sieve[j]=1;
}
}
}
long T;
scanf("%ld",&T);

while(T--)
{
scanf("%ld %ld",&t1,&t2);
long prim=0;
for(long I=t1 ; I<=t2 ; I++)
{
if(sieve[I]==0)
{
if(sieve[rev(I)]==0)
prim++;
}
}
printf("%ld\n",prim);
}
return 0;
}

``````

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

Hi,
boss
Here is my code:

Code: Select all

``````#include<cstdio>
#include<cstring>
bool sieve={0};
bool prim={0};
long rev( long I )
{
long sum=0,num=I;
while(num!=0)
{
sum+=num%10;
num=num/10;
}
return sum;
}

int main()
{
long t1,t2;
long i,j;
prim=1;
sieve=1; sieve=1;
for(i=3 ; i<=1000000 ; i+=2)
{
sieve[i+1]=1;
if(sieve[i]==0 && i<=1000)
{
for(j=i*i ; j<=1000000 ; j+=2*i)
{
sieve[j]=1;
}
}
}
for(long I=3 ; I<=1000000 ; I+=2)
{
if(sieve[I]==0)
{
if(sieve[rev(I)]==0)
prim[I]=1;
}
}

long T;
scanf("%ld",&T);

while(T--)
{
scanf("%ld %ld",&t1,&t2);
long pr=0,st;
if(t1<=2 && t2>=2)
{
st=3;
pr++;
}
else if(t1%2==0 && t1>=3)
{
st=t1+1;
}
else st=t1;
for(long I=st ; I<=t2 ; I+=2)
{
if(prim[I]==1)
{
pr++;
}
}
printf("%ld\n",pr);
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA