SPOJ: Prime Generator -- PRIME1

Problem Description

Click here for SPOJ link: PRIME1

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.

Sample Input/Output

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

Time limit: 6s
Source limit: 50000B
Memory limit: 256MB

Solution description of Prime Generator(PRIME1) 

This solution of this problem is direct implementation of Sieve of Eratosthenes method of generating prime numbers. To determine if a number is prime or composite number, we often have to experiment by dividing by primes from a list of primes. We divide by 2, 3, 5, etc. And if none of these divisions comes out even, then our number is a prime.

This is a very simple method for making a list of primes. Here are the steps to find all prime numbers less than or equal to a given integer n by Sieve of Eratosthenes method:

  1. First create an array of consecutive integers from 2 to n: (2, 3, 4, ..., n).
  2. let p be an integer variable, initialize it with 2, the first prime number.
  3. Starting from p, count up in increments of p and cross out all the multiples of p less than or
      equal  to n (2p, 3p, 4p .... kp <= n).
  4. Take the first number greater than p in the array that is uncrossed. If there is no such number
      <= n,then stop. Otherwise, assign this new number in p (which is the next prime), and start
      from step 3.

Solution of Prime Generator(PRIME1)in C

#include<stdio.h>
/**
*  SPOJ: Prime Generator -- PRIME1
*/

int prime[10000],primes;

void init_primes(){
     static int isprime[32000];
     int i,j;
     for(i=2;i<32000;i++) isprime[i]=1;
     for(i=2;i*i < 32000;i++)if(isprime[i])
     {
         for(j=2*i;j<32000;j+=i) isprime[j]=0;        
     }
     primes=0;
     for(i=2;i<32000;i++)
        if(isprime[i]) 
            prime[primes++]=i;
}

int seive[100001];

void find_seive(int lo, int hi){
   int i,j,p,n;
   for(i=0; i<=hi-lo; i++) 
       seive[i]=1;
   for(j=0;;j++){
       p=prime[j];
       if(p*p > hi) break;
       n = (lo/p)*p;
       if(n<lo) n+=p;
       if(n==p) n+=p;
       for(;n<=hi; n+=p) 
          seive[n-lo]=0;         
   }  
}

int main(){
    int cases,caseno,lower,upper,i;
    init_primes();
    scanf("%d",&cases);
    for(caseno=0;caseno<cases;caseno++){
        if(caseno) printf("\n");
        scanf("%d%d",&lower,&upper);
        if(lower<2) lower=2;
        find_seive(lower,upper);
        for(i=0; i<=upper-lower; i++)
            if(seive[i]){
               printf("%d\n",lower+i);
            }                               
    }
    return 0;
}