SPOJ: Prime1 - Programmers Heaven

#### Howdy, Stranger!

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

# 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???
• IndianPosts: 1Member
edited March 2014

This was my code and i still get the Time Limit Exceeded warning for the PRIME1 problem in SPOJ:
Any solutions yet?

# include<stdio.h>

int main(void)
{
int i,j,k,n;
long int l,a[10],b[10];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%ld %ld",&a[i],&b[i]);
}
for(i=0;i<n;i++)
{
for(l=a[i],j=0;l<=b[i];l++,j=0)
{
k=1;
while(k<=l)
{
if(l%k==0)
j++;
k++;
}
if((j<=2)&&(l!=1))
printf("%ld\n",l);
}
printf("\n");
}
return 0;
}