10200  Prime Time
Moderator: Board moderators
10200TLE 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=ba+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;
}
#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=ba+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
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 isprimecall, 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.
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 isprimecall, 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.
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.
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.
About Floating Point
I Think This Is Enough To Print The Result In Normal C Expression For Floating Ponit . Like This >
GOOD LUCK
ROCKY
Code: Select all
printf("%.2lf\n",result);
ROCKY
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[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)(ba+1)) * 100);
}
return 0;
}
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 :
or
Would you please give me a bit explanation?
Code: Select all
bool array_name[100010041];
Code: Select all
char array_name[100010041];
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=p2p1+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]=2is_prime;
}
if(is_prime==1)
wyn++;
}
per=wyn/ile*100;
printf("%.2f\n",per);
}
}
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=p2p1+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]=2is_prime;
}
if(is_prime==1)
wyn++;
}
per=wyn/ile*100;
printf("%.2f\n",per);
}
}

 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=ba+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;
}
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=ba+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;
}