#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

Welcome to the new platform of Programmers Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use it's exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# SPOJ: Prime1

Posts: 69Member
Hello Everybody,

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

[code]
#include
#include

int main()
{
int a, b, c = 1, test,root,v;
scanf("%d",&test);
while(test!=0)
{
scanf("%d%d",&a,&b);
printf("
");
while(a<=b)
{
if (a==2 || a==3)
{
printf("%d
",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
",a);
a++;
}
test--;
}
return 0;
}[/code]

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

· ·

• Posts: 3,711Member
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.)
· ·
• Posts: 69Member
I tried to consider above stated ideas....and impleamented the following code...
But still get the same result...
[code]
#include

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
");
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
",a); //print if c==0 else continue.
}
}
}
[/code]

Help me, Waiting for Replies...
Where am I slow?? This code is teasing my mind.
· ·
• Posts: 69Member
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???
· ·