Time exceeded error on SPOJ

Question

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

here is the link http://www.spoj.com/problems/PRIME1/

I came up with this solution but its showing time exceeded error, so how can i improve it?

 #include<stdio.h>
 int main()
    {
      int n,a,i,b;
      scanf("%d",&i); 
      while(i>0){
        scanf("%d",&a);
        scanf("%d",&b);
        while(a<=b){    
            for(n=2;n<=a;n++){
            if(a%n==0)break;
            }
            if(a==n){
            printf("%d\n",a);
            }
        a++;
        }
    i--;
    printf("\n");
}
return 0;   
}

Linking to a live site is not useful for future interest in this question.. please add a Fiddle.. — JF it, Jul 11 '14 at 13:01

Ivaylo Strandjev · Answer 1 · 2014-07-11T13:37:13.363

0

You need to apply sieve of Eratosthenes to solve the problem in the given time constraints. Checking if each number is prime one by one will be way too slow.

EDIT: in fact the sieve should be segmented, not a full sieve of eratosthenes.

edited Jul 11 '14 at 13:37

answered Jul 11 '14 at 12:46

Ivaylo Strandjev

69,226
18
123
176

"m <= n <= 1000000000, n-m<=100000" - that's a wrong approach. – Karoly Horvath Jul 11 '14 at 13:03
@KarolyHorvath not only that it is not a wrong approach but I've also solved the very same problem with this approach. Still maybe I need to mentioned that a [segmented sieve](http://stackoverflow.com/q/10249378/812912) should be used. – Ivaylo Strandjev Jul 11 '14 at 13:34

score 0 · Accepted Answer · edited May 23 '17 at 11:51

The simplest fast way to calculate primes is to use the Sieve of Erastothenes. The algorithm is to:

1)Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
2)Initially, let p equal 2, the first prime number.
3)Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).
4)Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

For this problem you would need to use Segmented Sieve of Erastothenes. Check the link for details.

SoE Algorithm from wikipedia(Sieve of Erastothenes).

Time exceeded error on SPOJ

2 Answers2