## 10200 - Prime Time

Moderator: Board moderators

mahbub.cse.kuet
New poster
Posts: 3
Joined: Thu Sep 03, 2009 8:53 pm

### 10200 Prime Time

From other post i knew that EPS should add to avoid small precision error. I also Added EPS. BUT WRONG ANSWER. WHY ??????
MY CODE IS BELOW:

Code: Select all

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

#define EPS 1e-10

using namespace std;

unsigned long prime[4000];
unsigned long total_prime=2;

int Is_prime(unsigned long num)
{
unsigned long root = sqrt(num);
for(int i=0; prime[i] <= root; i++)
if(!(num % prime[i]))
return 0;
return 1;
}

void PRIME_NUM_GENERATOR()
{
unsigned long num;
int Is_p, i;
unsigned long ele = 2;

prime[0] = 2;
prime[1] = 3;

for(num = 4; num <=20000; num++) {
Is_p = 1;
for(i =0; prime[i] <= sqrt(num); i++)
if(!(num % prime[i])) {
Is_p = 0;
break;
}
if(Is_p) {
prime[ele++] = num;
total_prime++;
}
}
}

int main()
{
unsigned long a, b, i;
double actual_prime, gen_prime;

PRIME_NUM_GENERATOR();

while(scanf("%ld %ld", &a, &b) == 2) {
actual_prime = gen_prime = 0;

for(i=a; i<=b; i++) {
gen_prime++;
if(Is_prime(i*i+i+41))
actual_prime++;
}
printf("%.2lf\n", ((actual_prime/gen_prime) * 100)+EPS);
}

return 0;
}``````
[/color][/size]

shiul
New poster
Posts: 3
Joined: Thu Jun 10, 2010 2:09 pm
Location: COLOMBIA- Barranquilla

### Re: 10200 - Prime Time

somebody realice this problem in JAVa I need help !

my code is TLE and i dont know why

i try with this cases test :

0 10000
40 40
1 10000
1 9999
0 9999
551 1807
3957 8978
2784 8208
8138 9707
3965 8178
843 8651
6055 9655
6399 8052
7362 8656
742 1185
2145 6359
3607 8999
6423 9662
5536 8242
1294 4157
32 99
932 4566
6155 7063
2196 5454
894 7486
8169 9119
9498 9894
2091 3582
7027 8695
164 9213
3814 8954
1810 3579
1650 5141
2250 8761
4747 7461
1490 6101
957 6483
3141 8145
2401 8385
5665 8128
187 2029
6026 7065
711 2433
5470 8488
7636 9741
1296 5452
5506 9657
3219 5235
2838 9813
4202 8091
3564 9268
500 9304
5166 7917
2950 3090
1686 5950
628 6788
2655 2684
3140 6826
249 5728
4621 6984
3983 8015
531 7121
4968 9176
7793 9508
8794 8798
2107 3331
1157 3939
2117 5647
6225 7135
6335 6781
4513 5934
5284 5362
1598 9093
7689 8254
6837 9504
992 9795
1291 6271
137 531
648 2779
5727 8757
1078 8805
1669 5237
1376 4944
383 4534
5833 6562
3279 7137
7064 7268
5058 6954
1540 5658
1411 8357
2604 6124
8124 8216
1388 8784
4672 8726
3468 8990
1040 1899
3925 8580
1135 2813
174 8908
1795 9827
2482 7880
5020 5164
1017 2412
1327 8812
1560 1971

shiul
New poster
Posts: 3
Joined: Thu Jun 10, 2010 2:09 pm
Location: COLOMBIA- Barranquilla

### Re: 10200 - Prime Time

somebody was realice the problem 10200 in java i need help please !

fkrafi
New poster
Posts: 13
Joined: Wed Sep 15, 2010 1:36 pm

### Re: 10200 - Prime Time

Why i am getting wa....

Code: Select all

``````AC
``````

shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

### Re: 10200 - Prime Time

Last 3 days was the worst nightmare in my life.... I was trying to Got this problem AC but No way.... My solution was at 1st TLE then RTE and after dat WA!!!...
Itz getting WA at .120 sec (May b the last second of judgment)... I cn't sleep eat and concentrate on my study.... Plzz I m seriously in need of help....

Code: Select all

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

void seive();
long int prm[10001];

int main()
{

long i,j,a,b,p,s,count,tag;
double res;

seive();

while(scanf("%ld %ld",&a,&b)!=EOF)
{
count=0;
for(i=a;i<=b;i++)
{
p=i*i+i+41;

s=sqrt(p);

tag=0;

for(j=0;prm[j]<=s;j++)
if(p%prm[j]==0)
{
tag=1;
break;
}

if(tag==0)
count++;
}

res=(double)count*100/(b-a+1);

printf("%.2lf\n",res+1e-7);

}

return 0;
}

void seive()
{

long int i,j,k,a[104745],lim=104745;

a[0]=0;
a[1]=1;
a[2]=1;

for(i=3;i<lim;i+=2)
{
if(i%2!=0)
{
a[i]=0;
}
}

prm[0]=2;
k=1;

for(i=3;i<lim;i+=2)
{
if(a[i-1]!=0)
{
prm[k++]=i;

for(j=2;i*j<lim;j++)
{
a[(i*j)-1]=0;
}
}
}

return;
}
plz somebody....anybody help me.... :(  :(
``````
I'll keep holding on...Until the walls come tumbling down...And freedom is all around .....

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

### Re: 10200 - Prime Time

I got Accepted just after adding 1e-8 to the result.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

thnkndblv
New poster
Posts: 2
Joined: Sat Aug 13, 2011 11:26 pm

### Re: 10200 - Prime Time

Maybe you need print the output like this:

printf ("%.2lf\n", (cnt * 100.0) / (double)(b - a + 1) + 1e-9);

nazmus_20000
New poster
Posts: 7
Joined: Fri Dec 14, 2012 9:01 pm

### 10200 - Prime Time

don't really get it why RTE....plz can anyone help plz.....

#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
long long int a[10010],b[10010];
void prime()
{
long long int i,j;
for(i=2;i*i<=10000;i++)
{
if(a==0)
{
for(j=i*i;j<=10000;j+=i)
{
a[j]=1;
}
}
}
for(i=2,j=0;i<=10000;i++)
{
if(a==0)
{
b[j]=i;
j++;
}
}
}
int check(long long int n)
{
long long int t,i,j;
t=n*n+n+41;
j=sqrt(t);
for(i=0;b<=j;i++)
{
if(t%b==0)return 1;
}
return 0;
}
int main()
{
long long int i,j,k,l,d,c;
prime();
while(scanf("%lld %lld",&d,&c)!=EOF)
{
for(i=d,k=0;i<=c;i++)
{
j=check(i);
if(j==0)k++;
}
printf("%.2lf\n",(k*100.0)/(double)(c-d+1)+1e-7);
}
return 0;
}

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

### Re: 10200 - Prime Time

You could run check() for all n once and store the results in an array.
Check input and AC output for thousands of problems on uDebug!

Nut_Boltu
New poster
Posts: 10
Joined: Wed Dec 12, 2012 7:47 pm

### Re: 10200 - Prime Time

First i got WA/Now i m getting RE.anyone plz help.

Code: Select all

``````#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
long int prime [100010043];

bool IsPrime(long int num)
{
for(long int i=3;i<=sqrt(num);i+=2)
{
if(!(num%i)) return false;
}
return true;
}
void PreGeneratePrime()
{
long int value;
for(int n=0;n<=10000;n++)
{
value = n*n+n+41;
if(IsPrime(value)) prime[value]=1;
}
}
int main()
{
int a,b;
PreGeneratePrime();
long int value;
double result,numofPrime;
while(cin>>a>>b)
{
numofPrime =0;

for(int i=a;i<=b;i++)
{
value = i*i+i+41;
if(prime[value])numofPrime++;
}
result = (numofPrime*100.0)/(b-a+1);
printf("%0.2lf\n",result);
}

return 0;
}

``````

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

### Re: 10200 - Prime Time

Your might be trying to allocate too much memory.
Check input and AC output for thousands of problems on uDebug!

Nut_Boltu
New poster
Posts: 10
Joined: Wed Dec 12, 2012 7:47 pm

### Re: 10200 - Prime Time

thanks brianfry713. i changed the data type from long int to int.
and also changed the line " printf("%0.2lf\n",result);" to "printf("%0.2lf\n",result+1e-7);".
Got AC.

try_tired
New poster
Posts: 6
Joined: Thu Jan 23, 2014 3:22 am

### Re: 10200 - Prime Time

import java.io.*;
import java.math.*;
import java.util.*;
public class bigdigit {
public static void main(String[] args)throws IOException
{
try{
Scanner sc = new Scanner(System.in);
int i,j,n;
BigInteger g,fact;
long nw,m;
n=sc.nextInt();
for(i = 1;i <= n;i++)
{
fact = BigInteger.valueOf(1);
nw = sc.nextLong();
for(j = 1;j <= nw;j++)
{
fact = fact.multiply(BigInteger.valueOf(j));
}

m = 0;
g = BigInteger.valueOf(0);
while(true)
{
fact = fact.divide(BigInteger.valueOf(10));
m++;
if(g == fact)
break;
}
System.out.println(m);
}

}catch(Exception e)
{
System.out.println("Error");
}
}

}

UVa problem number : 1185
why i get time limit here?
pls help me.

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

### Re: 10200 - Prime Time

Try using BufferedReader and BufferedWriter, also use class Main
Check input and AC output for thousands of problems on uDebug!

thewill
New poster
Posts: 6
Joined: Wed Dec 04, 2013 10:18 am

### Re: 10200 - Prime Time

why am i getting WA for this code anybody helpplzz i am fedup

#include<iostream>
#include<cstdio>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>
#include<deque>
#include<iterator>
#include<assert.h>
#include<bitset>
#include<climits>
#include<ctime>
#include<complex>
using namespace std;
int isprime(long int n)
{
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
return 0;
}
}
return 1;
}
int main()
{
int i,j,m,n;
int cnt,check;
bool a[1000000];
int b[10010];
long int s,l;
memset(b,0,sizeof(b));
for(i=0;i<1000000;i++)
{
a=true;
}
a[0]=a[1]=false;
for(i=2;i<1000000;i++)
{
if(a==true)
{
for(j=2;j*i<1000000;j++)
{
a[j*i]=false;
}
}
}
for(i=0;;i++)
{
l=i*i + i +41;
if(l>1000000)
{
break;
}
if(a[l]==true)
{
b=1;
}
}
for(j=i;;j++)
{
l=j*j +j +41;
if(j>10005)
{
break;
}
if(isprime(l))
{
b[j]=1;
}
}
while(cin>>m>>n)
{
cnt=0;
for(i=m;i<=n;i++)
{
if(b==1)
{
cnt++;
}
}
printf("%.2f\n",(float)cnt*100.00/(n-m+1));
}
return 0;
}