Page 6 of 8
Re: 10533 - Digit Primes
Posted: Fri Aug 01, 2008 9:11 pm
by Nishith csedu 1448
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 !!!!!!!!!!!!!!
Re: 10533 - Digit Primes
Posted: Tue Aug 05, 2008 6:54 am
by Obaida
Thanks Nishith you helped me a lot!!!
Re: 10533 - Digit Primes
Posted: Fri Aug 22, 2008 5:36 pm
by GUC.HassanMohamed
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.
Thanks in advance.
Code: Select all
import java.io.*;
import java.util.*;
public class DigitPrimes {
static boolean [] a=new boolean [1000001];
static int [] dp = new int [1000001];
public static void main(String[] args) throws IOException{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader (isr);
int times = new Integer(br.readLine());
getPrime(a);
for(int i = 0 ; i < times ;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
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[0]=a[1]=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];
}
}
10533 - Digit Primes
Posted: Thu May 14, 2009 11:25 am
by dipal
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[1000100]={0};
long long dt[1000100]={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[0]=data[1]=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
Re: 10533 - Digit Primes
Posted: Tue Nov 10, 2009 5:42 pm
by sms.islam
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?
please help me.
thanx
Re: 10533 - Digit Primes
Posted: Mon Dec 21, 2009 10:25 am
by masum.shafayat
Code: Select all
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
bool prime[1000000];
long i,j;
for(i=2;i<=1000000;i++)
prime[i]=true;
prime[0]=false;
prime[1]=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.
Re: 10533 - Digit Primes
Posted: Wed Dec 29, 2010 10:10 am
by chris benoit
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;
}
Re: 10533 - Digit Primes
Posted: Fri Dec 31, 2010 3:15 pm
by helloneo
See some previous posts..
There are answers for the TLE issue
Online Casino
Posted: Tue Jan 25, 2011 5:35 pm
by AlexWolfen
Mike are you there?
Re: 10533 - Digit Primes
Posted: Sun Aug 07, 2011 1:48 pm
by plamplam
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
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
10533 Digit Primes (TLE) why? please help me, please
Posted: Sat Jan 07, 2012 12:37 pm
by uvasarker
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[1000000];
int main()
{
long i,j,t1,t2;
sieve[0]=sieve[1]=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;
}
Re: 10533 Digit Primes (TLE) why? please help me, please
Posted: Wed Jan 11, 2012 9:47 pm
by brianfry713
Re: 10533 Digit Primes (TLE) why? please help me, please
Posted: Sat Jan 28, 2012 10:40 am
by uvasarker
I am still getting TLE. Please, help me. My updated code is here:
Code: Select all
#include<cstdio>
#include<cstring>
bool sieve[10001011]={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[0]=1; sieve[1]=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;
}
Re: 10533 Digit Primes (TLE) why? please help me, please
Posted: Sat Feb 11, 2012 9:24 am
by uvasarker
Hi,
boss
I update more on this problem but still TLE.Please help me please, please, please, please, please.
Here is my code:
Code: Select all
#include<cstdio>
#include<cstring>
bool sieve[10001011]={0};
bool prim[1000000]={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[2]=1;
sieve[0]=1; sieve[1]=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;
}
Re: 10533 Digit Primes (TLE) why? please help me, please
Posted: Tue Feb 14, 2012 12:04 am
by brianfry713
Precompute an array of size 1000000 that counts the number of digit primes up to that point. Your main I/O loop should just subtract the count of t1 from the count of t2.