Page 5 of 14
10200-TLE pls help
Posted: Fri May 06, 2005 3:00 pm
by 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;
}
Posted: Fri May 06, 2005 4:50 pm
by 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.
Posted: Fri May 06, 2005 8:50 pm
by 59557RC
yeah!!thanx i got AC
Posted: Wed Sep 07, 2005 10:55 pm
by jjtse
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?
Posted: Thu Sep 08, 2005 12:28 am
by 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.
Posted: Thu Sep 08, 2005 8:30 am
by 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]?)
Posted: Thu Sep 08, 2005 8:37 am
by jjtse
thanks,
I already solved it.
About Floating Point
Posted: Thu Sep 08, 2005 12:15 pm
by Rocky
I Think This Is Enough To Print The Result In Normal C Expression For Floating Ponit . Like This ->
GOOD LUCK
ROCKY
Posted: Fri Sep 23, 2005 12:45 pm
by dumb dan
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.
10200
Posted: Thu Sep 29, 2005 9:49 am
by 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;
}
Posted: Thu Sep 29, 2005 9:51 am
by Larry
You can remember the results of "isPrime".
Posted: Thu Sep 29, 2005 9:55 am
by 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 :
or
Would you please give me a bit explanation?
Prime Time strange WA :(
Posted: Mon Nov 28, 2005 4:58 pm
by 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);
}
}
Posted: Sun Dec 04, 2005 9:48 pm
by sectroyer
I have already spoted my error
I didn't add 1 after sqrt
10200 Time Limit Exceeded (need help)
Posted: Mon Jan 30, 2006 4:39 pm
by 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;
}