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

- Assume that all numbers (from 2 to
*n*) are prime. - Then take the first prime number and removes all of its multiples.
- 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);
}
```

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow