# 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);
}
`````` PDF - Download math for free