Skip to the content of the web site.
## Lesson 149u: Sieve of Eratosthenes

Suppose you wanted to find all prime numbers less than or equal to a given
number $N$. The easiest way to do this is to create an array
that can hold the integers from $1$ to $N$. We will initialize
the array so that `array[k] == k`. If we ever determine that
a number `k` is not prime, we will assign `array[k] = 0;`.
By definition, $1$ is not prime, so we will immiedately assign
`array[1] = 0;`. Next starting with $2$, if we determine
that `k` is prime (meaning that `array[k] == k`, we
have then determined that all integer multiples of `k` up until
the end of the array to be composite, so we set:

`
array[2*k] = 0;
array[3*k] = 0;
array[4*k] = 0;
array[5*k] = 0;`

.

.

.

until we reach the end of the array.

We then search forward in the array until we find the next `k`
such that `array[k] == k` and repeat the above process.

This is called the Sieve of Eratosthenes. Implement a function that prints all prime numbers up to but not exceeding $N$ in the format:

`2, 3, 5, 7, 9, 11, 13, ...`

Be sure not to have a comma after the last prime number. Your function declaration should be:

void print_primes( unsigned long N );

As an aside, why is $1$ not prime? In general, many of the most
interesting properties of prime numbers are not true if $1$ is considered
to be prime. For example, that every number has a unique prime factorization
is false if $1$ is a prime, for $6 = 2 \times 3 = 2 \times 3 \times 1 = 2 \times 3 \times 1 \times 1 \times \cdots$. Thus, if $1$ were said to be prime,
then almost every interesting theorem about prime numbers would have to
be worded as *all prime numbers except for $1$*.

In the previous function, you could have easily printed the prime
number every time you found one. You would start by automatically printing
`"2"`, and then for every subseuent prime number ` n`
you find, print

If you have found $n$ primes less than or equal to $N$, return an array of size $n$ containing those $n$ prime numbers.

Now, beause you don't know how large an array to build, you will have
to temporarily store prime numbers, and the easiest way is to look at
the array `array`; however, looking through the entire array of
capacity $N$ to find $n$ primes is unnecessarily expensive, especially
when you know mathematically that the number of primes less than or
equal to $N$ will be approximately $n \approx \frac{N}{\ln(N)}$.
This estimates there are approximately $72382$ prime numbers less than
or equal to one million. There are in fact $78498$ primes less than
or equal to one million, so this approximation is not unreasonable;
however, it is not exact.

It can be shown that the relative error drops at approximately
$0.24 n^{-0.085}$, so the relative error actually goes to zero
as $n$ becomes large.

Devise a scheme whereby you use the existing array to store all the prime numbers without having to walk through the entire array to retrieve all of them.

Array<unsigned long> *primes( unsigned long N );