10200 - Prime Time

[59557RC]

i dont understand why i got TLE all the time when dealin with prime numbers.pls anyone tell me whats wrong with my code for 10200 :
#include <stdio.h>
#include <math.h>


int isprime(long num);

int main()

{

int a,b,i,prime,tot;
long res,j,n;
double per,t,p;

while(scanf("%d %d",&a,&b)!=EOF){
prime=0;
for(i=a;i<=b;i++){

n=i*i+i+41;
res=isprime(n);

if(res==1) prime++;
}



t=b-a+1;p=prime;
per=p/t;
printf("%.2lf\n",per*100);



}

return 0;
}

int isprime(long num)

{
long k,m,f=0;
if(num==2) return 1;
else if(num%2==0) return 0 ;

m=sqrt(num);
for(k=3;k<m;k+=2){
if(k%3==0 || k%5==0 || k%7==0 || k%11==0 && k>3) continue;
if(num%k==0) return 0;
}
if(num%k!=0) return 1;

return 0;

}

[dumb dan]

The first thing you should do is remove this line:
if(k%3==0 || k%5==0 || k%7==0 || k%11==0 && k>3) continue;

I assume you were trying to save time, but all that line accomplishes is making sure you do between 1 and 5 modulos each step in the loop instead of just 1 modulo. Removing that line alone will make your program about 3 times faster.

Secondly it's always a good idea to precalc primes (in this case up to sqrt(10000^2+10000+41)). So when you need to check if n is prime, you only need to try to divide it by all primes between 2 and sqrt(n) instead of trying to divide it with all odd numbers.

Further optimizing can be done by saving results from the isprime-call, so you never call this function on the same number more than once. I doubt you need to do that to get AC though. One could even save the result for ranges of numbers, but that's probably overdoing it.

[59557RC]

yeah!!thanx i got AC

[jjtse]

(in this case up to sqrt(10000^2+10000+41)).

That's a good idea, but where are you going to find an array big enough to hold a bazillion prime numbers?

[jjtse]

sohel's idea sounds good, and exactly what I implemented. I created an array of size 11000 that holds prime numbers up to 11000. (the array doesn't get filled up all the way because not every number is prime).

However, I still get time limit exceeded. I'm thinking just enumerating prime numbesr from 1 - 10000 will take quit a bit of time in itself. I've seen several posts about listing prime numbers in an array. They tried it and got accepted, but for some reason, mine takes 10.088 secs to run. It is still getting TLE error.

[mf]

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]?)

[jjtse]

thanks,

I already solved it.

[Rocky]

I Think This Is Enough To Print The Result In Normal C Expression For Floating Ponit . Like This ->

Code: Select all

printf("%.2lf\n",result);

GOOD LUCK
ROCKY

[dumb dan]

That's a good idea, but where are you going to find an array big enough to hold a bazillion prime numbers?

By sqrt(10000^2+10000+41), I mean the square root of (10000^2+10000+41). Which is 10001. And in the range from 2 to 10001 there are only 1229 prime numbers.

[Faisal_Bd]

I tried my best but could not get this problem AC within the time limit, let alone with a good timing... Please just have a look on my code and tell me how I can get this problem AC with a good timing.

Code: Select all

#include <stdio.h>

#define MAX 10100

int primes[1250];
int nPrimes;

void generatePrimes(void)
{
	int isPrime; /* flag */
	int i, j;

	primes[0] = 2;
	nPrimes = 1;
	for (i = 3; i < MAX; i+=2) {
		isPrime = 1;
		for (j = 0; j < nPrimes && primes[j]*primes[j] <= i; j++) {
			if (!(i%primes[j])) {
				isPrime = 0;
				break;
			}
		}

		if (isPrime) {
			primes[nPrimes++] = i;
		}
	}
}

int isPrime(int n)
{
	int i;

	if (n == 2) {
		return 1;
	}
	if (!(n%2)) {
		return 0;
	}

	for (i = 1; i < nPrimes && primes[i]*primes[i] <= n; i++) {
		if (!(n % primes[i])) {
			return 0;
		}
	}

	return 1;
}

int main(void)
{
	int a, b; /* lower and upper limit of the range respectively */
	int count; /* counts number of primes in the given range */
	int i;

	generatePrimes();

	while (scanf("%d %d", &a, &b) != EOF) {
		count = 0;
		for (i = a; i <= b; i++) {
			if (isPrime(i*i + i + 41)) {
				count++;
			}
		}
		printf("%.2lf\n", ((double)count / (double)(b-a+1)) * 100);
	}
	return 0;
}

[Larry]

You can remember the results of "isPrime".

[Faisal_Bd]

How can I remember the results of isPrime()? for n = 10000, I have to check whether n*n + n + 41 is a prime number. So far I know, I can't declare so big array :

Code: Select all

bool array_name[100010041];

or

Code: Select all

char array_name[100010041];

Would you please give me a bit explanation?

[sectroyer]

Hi I have tested my code against many inputs and I am still unable to find a bug
I hope someone will help me.

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

#define ilosc 20001
int main(int argc, char *argv[])
{
int i1,i2,p1,p2,up,is_prime;
char pri[ilosc];
unsigned long long int form;
float per,wyn,ile;
memset(pri,0,ilosc);
while(scanf("%d %d",&p1,&p2)==2)
{
wyn=0;
ile=p2-p1+1;
if(p1 > p2)
{
wyn=p1;
p1=p2;
p2=wyn;
wyn=0;
}
for(i1=p1;i1<=p2;i1++)
{
is_prime=1;
if(i1 < ilosc)
{
if(pri[i1]==1)
{
wyn++;
continue;
}
else if(pri[i1]==2)
continue;
}
form=i1*i1+i1+41;
up=floor(sqrt(form));
for(i2=2;i2<=up;i2++)
{
if((form%i2)==0)
{
is_prime=0;
break;
}
}
if((i1 < ilosc) && (pri[i1]==0))
{
pri[i1]=2-is_prime;
}
if(is_prime==1)
wyn++;
}
per=wyn/ile*100;
printf("%.2f\n",per);
}
}

[sectroyer]

I have already spoted my error
I didn't add 1 after sqrt

[athlon19831]

I don't know why i always got Time Limit Exceeded.
My code:
#include "iostream.h"
#include "stdio.h"
#include "math.h"
#include "string.h"
int main(int argc, char* argv[])
{
long a,b,i,j,k,num,l;
double t;
double sum;
while(cin>>a>>b)
{
num=0;
l=b-a+1;
for(i=a;i<=b;i++)
{
j=i*i+i+41;
t=sqrt(j);
for(k=2;k<=t;k++)
{
if(j%k==0)
{
k=j;
}
}
k--;
if(k<t)
{
num++;
}
}
sum=1.0*l;
sum=(num/sum)*100;
printf("%0.2f",sum);
cout<<endl;
}
return 0;
}