10200 - Prime Time

[Jan]

Search the board first. Don't open a new thread if there is one already.

[x140l31]

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] = 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[40] = 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]

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]

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

Code: Select all

Removed because Accepted!

[x140l31]

newton have you tried without "eps"?

some people had WA because of this...

[newton]

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

[ishtiaq ahmed]

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.

[newton]

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

[x140l31]

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]

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]

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 

thanx in advance

[newton]

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;
4. scan inputs and get your answer.

[sreejond]

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 .
please brother help me.

here is my code:

Code: Select all

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

long x,y,count,p,store[10009],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]

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.

[calicratis19]

deleted .....AC