## 10200 - Prime Time

Moderator: Board moderators

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

### 10200-TLE pls help

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

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
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
Contact:
yeah!!thanx i got AC
aaa

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

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

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
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
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

### 10200

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;
int nPrimes;

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

primes = 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:
You can remember the results of "isPrime".

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 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;``
or

Code: Select all

``char array_name;``
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 :(

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
I have already spoted my error I didn't add 1 after sqrt athlon19831
New poster
Posts: 20
Joined: Thu Jan 19, 2006 2:32 pm

### 10200 Time Limit Exceeded (need help)

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