math Prime sieve


Example

The Sieve of Eratosthenes generates all the primes from 2 to a given number n.

  1. Assume that all numbers (from 2 to n) are prime.
  2. Then take the first prime number and removes all of its multiples.
  3. Iterate the step 2 for next prime. Continue until all numbers till n have been marked.

Pseudocode:

Input: integer n > 1
 
Let A be an array of Boolean values, indexed by integers 1 to n,
initially all set to true.
 
for i = 2, 3, 4, ..., not exceeding sqrt(n):
    if A[i] is true:
        for j = 2i, 3i, 4i, 5i, ..., not exceeding n :
            A[j] := false
 
Output: all i such that A[i] is true.

C code:

void PrimeSieve(int n)
{
    int *prime;
    prime = malloc(n * sizeof(int));
        int i;
        for (i = 2; i <= n; i++)
            prime[i] = 1;    
    
       
    int p;
    for (p = 2; p * p <= n; p++)
    {    
        if (prime[p] == 1) // a Prime found
        {
            // mark all multiples of p as not prime.
            for (int i = p * 2; i <= n; i += p)
                prime[i] = 0;
        }
    }
 
    // print prime numbers
    for (p = 2; p <= n; p++)
        if (prime[p] == 1)
            printf("%d ", p);
}