10200 - Prime Time

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Location: bangladesh
Contact:

10200-TLE pls help

Post by 59557RC » Fri May 06, 2005 3:00 pm

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;

}
aaa

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Fri May 06, 2005 4:50 pm

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
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Location: bangladesh
Contact:

Post by 59557RC » Fri May 06, 2005 8:50 pm

yeah!!thanx i got AC
aaa

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Wed Sep 07, 2005 10:55 pm

dumb dan wrote: (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
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Thu Sep 08, 2005 12:28 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Sep 08, 2005 8:30 am

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
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Thu Sep 08, 2005 8:37 am

thanks,

I already solved it.

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

About Floating Point

Post by Rocky » Thu Sep 08, 2005 12:15 pm

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

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Fri Sep 23, 2005 12:45 pm

jjtse wrote: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
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

10200

Post by Faisal_Bd » Thu Sep 29, 2005 9:49 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Sep 29, 2005 9:51 am

You can remember the results of "isPrime".

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

Post by Faisal_Bd » Thu Sep 29, 2005 9:55 am

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
New poster
Posts: 8
Joined: Mon Nov 28, 2005 4:55 pm

Prime Time strange WA :(

Post by sectroyer » Mon Nov 28, 2005 4:58 pm

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
New poster
Posts: 8
Joined: Mon Nov 28, 2005 4:55 pm

Post by sectroyer » Sun Dec 04, 2005 9:48 pm

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

athlon19831
New poster
Posts: 20
Joined: Thu Jan 19, 2006 2:32 pm

10200 Time Limit Exceeded (need help)

Post by athlon19831 » Mon Jan 30, 2006 4:39 pm

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;
}

Post Reply

Return to “Volume 102 (10200-10299)”