SPOJ: Prime1 - Programmers Heaven

Howdy, Stranger!

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

Categories

SPOJ: Prime1

VinayKhareVinayKhare Posts: 69Member
Hello Everybody,

[link=https://www.spoj.pl/problems/PRIME1/]Question is to Generate all Prime Numbers between two given Numbers.[/link]

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

Comments

  • LundinLundin 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.)
  • VinayKhareVinayKhare 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.
  • VinayKhareVinayKhare 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???
  • arjunmayilvagananarjunmayilvaganan 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;
    }

Sign In or Register to comment.