10533 - Digit Primes
Moderator: Board moderators
-
- 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 !!!!!!!!!!!!!!
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.............
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.
This may be the address of success.
-
- 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.
Thanks in advance.
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
i am not understanding what is problem with me.
im finding all output correct using my algo.
but why i am finding Wa. ??
Please somebody explain (used data as Prime Table (0 is prime) (1 is not prime));
thanx
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
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
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
-
- 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[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;
}
-
- 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......
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
See some previous posts..
There are answers for the TLE issue
There are answers for the TLE issue
-
- New poster
- Posts: 1
- Joined: Tue Jan 25, 2011 5:34 pm
- Location: United States
- Contact:
Online Casino
Mike are you there?
Re: 10533 - Digit Primes
Here are two input sets which helped me solve this problem.
Set 1:
Set 2:
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
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
-
- Learning poster
- Posts: 96
- Joined: Tue Jul 19, 2011 12:19 pm
- Location: Dhaka, Bangladesh
- Contact:
10533 Digit Primes (TLE) why? please help me, please
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10533 Digit Primes (TLE) why? please help me, please
Your Sieve method is too slow.
http://en.wikipedia.org/wiki/Sieve_of_E ... ementation
http://en.wikipedia.org/wiki/Sieve_of_E ... ementation
Check input and AC output for thousands of problems on uDebug!
-
- Learning poster
- Posts: 96
- Joined: Tue Jul 19, 2011 12:19 pm
- Location: Dhaka, Bangladesh
- Contact:
Re: 10533 Digit Primes (TLE) why? please help me, please
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;
}
-
- Learning poster
- Posts: 96
- Joined: Tue Jul 19, 2011 12:19 pm
- Location: Dhaka, Bangladesh
- Contact:
Re: 10533 Digit Primes (TLE) why? please help me, please
Hi,
boss
I update more on this problem but still TLE.Please help me please, please, please, please, please.
Here is my code:
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10533 Digit Primes (TLE) why? please help me, please
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.
Check input and AC output for thousands of problems on uDebug!