## 10200 - Prime Time

Moderator: Board moderators

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

### Re: 10200 PRIME TIME

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re:

mf wrote:If you do preprocessing a bit cleverly, you'll be able to solve each test case in just O(1) time.
(Hint: if you know that n^2+n+41 gives A primes for interval [0,a], and B primes for [0,b], what can you tell about the interval [a+1,b]?)

why doing it my program is slower? this code have 0.270 runtime:

Code: Select all

``````    VI p(10001, 1);
for (int i = 0; i < 40; i++) p[i] = i + 1;
p = 40;
for (int i = 41; i < 10001; i++)
p[i] = p[i - 1] + prime(formula(i));

int a, b;
while (cin >> a >> b)
{
if (a == 0) cout << (double(p[b])/double(b + 1))*100 << endl;
else
{
//calculate the result
}
}
``````
and this have 0.180 runtime:

Code: Select all

``````VI p(10001, 1);
p = 0;
for (int i = 41; i < 10001; i++)
{
p[i] = prime(formula(i));
}

int a, b;
while (cin >> a >> b)
{
double pr = 0;
for (int i = a; i <= b; i++) pr += p[i];

//calculate the result
}
``````
in both cases to "calculate the result" i do similar operations...

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

### Re: 10200 - Prime Time

it is WA.SOME ONE HELP ME PLZ.
HERE IS MY CODE:
#include<stdio.h>
#include<math.h>
#include<memory.h>
long store[10000+12];
void is_prime(void)
{
long result,k,i,j;

for(i=0;i<=10000;i++)
{
result=i*i+i+41;
if(result%2!=0)
{
j=(long)sqrt(result);
for(k=3;k<=j;k+=2)
{
if(result%k==0) break;
}
if(k>j) store=1;
}
}
}

int main()
{
int a,b,c;
int sum,ui;
double y;
double k,g;
memset(store,0,sizeof(store));
is_prime();

while(scanf("%d %d",&a,&b)!= EOF)
{
sum=0;
if(a>b)
{
ui=a;
a=b;
b=ui;
}

for(c=a;c<=b;c++)
{
if(store[c]==1)sum++;

}
g=b-a+1;
k=sum;
y=k/g;
printf("%.2f\n",y*100);
}

return 0;
}

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 10200 - Prime Time

Actually i had done a silly mistake.
for double i printed "%.2Lf\n" which would be "%.0lf\n".

Code: Select all

``Removed because Accepted!``
Last edited by newton on Wed Sep 03, 2008 5:51 pm, edited 2 times in total.
http://www.newton.0fees.net is enough! x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: 10200 - Prime Time

newton have you tried without "eps"?

some people had WA because of this...

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 10200 - Prime Time

x140131 wrote:
newton have you tried without "eps"?
some people had WA because of this...
yes i tried but failed!
is there anything wrong with my algorithm?

thanks
http://www.newton.0fees.net is enough! ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

### Re: 10200 - Prime Time

Your algorithms seems to be okay.You can try in this way
just change this section

Code: Select all

``````printf("%.2Lf\n",(cnt/(b - a + 1)*100.00)+eps);
``````
modifie to

Code: Select all

``````printf("%.2lf\n", ((cnt*100) / (b - a + 1)) + eps);
``````
You wouldn't need to use long double. Hope it will help you.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 10200 - Prime Time

Ishtiaq wrote:
printf("%.2Lf\n",(cnt/(b - a + 1)*100.00)+eps);
modifie to
printf("%.2lf\n", ((cnt*100) / (b - a + 1)) + eps);
that was not the bug i think.
however i changed but still WA
http://www.newton.0fees.net is enough! x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: 10200 - Prime Time

I've executed your program, and with

Code: Select all

``printf("%.2Lf\n",(cnt/(b - a + 1)*100.00)+eps);``
I have all wrong answers, with numbers very rare!!!!

have you tried all combinations?

Code: Select all

``printf("%.2lf\n",((cnt*100.00)/(b - a + 1))+eps);``

Code: Select all

``printf("%.2f\n",((cnt*100.00)/(b - a + 1))+eps);``

Code: Select all

``printf("%.2lf\n",((cnt*100.00)/(b - a + 1)));``

Code: Select all

``printf("%.2f\n",((cnt*100.00)/(b - a + 1)));``
....

debugger
New poster
Posts: 8
Joined: Tue Jul 29, 2008 6:24 pm

### Re: Fantastic

Joseph Kurniawan wrote:I

Code: Select all

``suggest to use "semi-hardcode".``

You are a very nice man. my idea is also like so.very nice.      Mohamed Abd El-Monem
New poster
Posts: 15
Joined: Mon Mar 31, 2008 1:20 am
Location: Egypt
Contact:

### Re: 10200 - Prime Time

Why TLE  I first generate all primes from 0 to 100010041 , and save them in array

then count the number of deprime from 0 to i from 0 to 10000

this is my code ,, any help please

Code: Select all

`` deleted ``
Last edited by Mohamed Abd El-Monem on Tue Sep 30, 2008 12:54 am, edited 1 time in total.

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 10200 - Prime Time

u need not to generate primes up to sqrt of 100010041 using sieve.
Just:

Code: Select all

``````             My Algorithm was

1. make an Boolean array of 10001
2. check isPrime( i*i + i + 41) for i-> 0 to MAX
3. set array[i] true if isPrime return true;
http://www.newton.0fees.net is enough! sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 10200 - Prime Time

lots of time get WA.
can anybody find the burg in my code.
i m sure enough about my algo & procedure.
tried lots of i/o.
but unsuccessful .

here is my code:

Code: Select all

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

long x,y,count,p,store,temp;
double res;

bool isPrime(long x)
{
if(x == 2) return true;
if(x == 1) return false;
if(x % 2 == 0) return false;
for(int i = 3; i*i<=x; i+=2){
if(x % i == 0) return false;
}
return true;
}

int main()
{
count=0;
for(int i=0;i<=10000;i++)
{
p=(i*i)+i+41;
if(isPrime(p))
count++;
store[i]=count;
}
while(scanf("%ld%ld",&x,&y)==2)
{
if(x>y)
{
temp=x;
x=y;
y=temp;
}
if(x==0 && y==0)
{
printf("100.00\n");
continue;
}
if(x==y)
{
if(store[x]==store[x-1])
{
res=((store[y]-store[x])/(y-x+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
}
if(store[x]!=store[x-1])
{
res=((store[y]-store[x]+1.0)/(y-x+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
else
{
res=((store[y]-store[x])/(y-x+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
}
return 0;
}
``````

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 10200 - Prime Time

if else series made the code more complex.u need not to precalculate count.

1. make store boolean.
2. set store[p] = isPrime[p] for 0 to MAX
3. replace ur code to..

Code: Select all

``````while(scanf("%d %d",&a,&b) == 2){
cnt = 0.0;
for(i = a; i<=b; i++){
if(store[i])
count = count + 1;
}
printf("%.2lf\n",(count*100.00/(b - a + 1)) + eps);
}``````
you need not to swap bcause a <= b.
int is enough for this problem.

why dont u practice using eps. its safe.
http://www.newton.0fees.net is enough! calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am