## C and C++

Moderators: None (Apply to moderate this forum)
Number of posts: 94715

This Forum Only

SPOJ: Prime1 Posted by VinayKhare on 20 Aug 2009 at 5:28 AM
Hello Everybody,

Question is to Generate all Prime Numbers between two given Numbers.

I have impleamented it number of ways....number of styles...but.....
Everytime I got the result "Time Limit Exceeded"

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

int main()
{
int a, b, c = 1, test,root,v;
scanf("%d",&test);
while(test!=0)
{
scanf("%d%d",&a,&b);
printf("\n");
while(a<=b)
{
if (a==2 || a==3)
{
printf("%d\n",a);
a++;
continue;
}
if ((a%2)==0 || (a%3)==0 || a<2)
{
a++;
continue;
}
root=(int)(sqrt(a)) + 1;
for(v=6;v<=root;v+=6)
{
if (a%(v-1)==0)
{
c = 0;
break;
}
if (a%(v+1)==0)
{
c = 0;
break;
}
}
if(c == 1)
printf("%d\n",a);
a++;
}
test--;
}
return 0;
}```

Can anyone help me speedup the code...
waiting for replies...
Thank You

Re: SPOJ: Prime1 Posted by Lundin on 20 Aug 2009 at 6:22 AM
How exactly do you clock the program?

I don't really grasp how your algorithm works, but here are some general suggestions:

Major optimization:
printf() is incredible slow, and if you clock the whole program you will only measure how sluggish printf() is, and not the speed of the actual algorithm.

sqrt() is also a slow function. As soon as you involve it, you involve float numbers, which are notoriously slow. Unless you have a real big amount of numbers to display, calling sqrt() will only make the program inefficient. Might be better to count from 2 to n/2 instead, even if it involves more iterations.

Make sure you never check if even numbers are prime numbers. That is pointless.

Minor optimization:
for loops are generally a tiny bit more efficient than while loops. You can iterate from max down to zero too, to save a few ticks (the CPU compares against zero more efficiently than it compares against a variable number).

(Also note that you cannot measure time accuately on hosted desktop environments like Windows and *nix, since they are not realtime systems.)
Re: SPOJ: Prime1 Posted by VinayKhare on 20 Aug 2009 at 11:47 AM
I tried to consider above stated ideas....and impleamented the following code...
But still get the same result...
```#include <stdio.h>

int main()
{
int test; // for Number of test cases.
long unsigned int a,b,i,c; // a first number, b second limit
scanf("%d",&test);
for(;test;test--)
{
scanf("%lu%lu",&a,&b);  //we have to find prime numbers between a and b
for(;a<=b;a+=2)
{
c=0;             //putting c=0 number is prime else not
if(a<2 || ( !(a%2) && a!=2) )
a++;   //if a is 1 or (even but not 2) increment by 1
if(a==2)
{
printf("2\n");
if(b==2)          //if upper limit is 2, don't print 3
break;
a++;
}
for(i=3;i<=( (a/2)+ 1);i+=2)
{
if(!(a%i))    //for loop is chekcing for prime upto (a/2)+1
{
c=1;
break;
}
}
if(!c)
printf("%lu\n",a);   //print if c==0 else continue.
}
}
}
```

Help me, Waiting for Replies...
Where am I slow?? This code is teasing my mind.
Re: SPOJ: Prime1 Posted by VinayKhare on 21 Aug 2009 at 11:00 PM
Hello Lundin,
Have you read my code? Can you please tell me, where am I wrong...why the code is not being accepted at spoj.pl. Why I always get the result "Time limit exceeded".

How could I develop the insight of creating more and more efficient algorithm.

What to learn, what to understand???

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic