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

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.)

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.

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???