Sieve of Eratosthenes

Generating primes

Given an integer $N$, you are asked to print all the prime numbers between $1$ and $N$.

Using what we have discussed so far, one way to do this would be to iterate over all the numbers from $1$ to $N$ and check if it’s prime or not.

Time Complexity - $O(N*\sqrt{N}).$

It should be okay for $N$ up to $10^4$ or even $10^5$ but not more.

---

Sieve of Eratosthenes

The Sieve of Eratosthenes is a simple algorithm to generate all primes from $1$ to $N$ in $O(N*log(logN))$.

Steps:

1. Create a list of all numbers from $2$ to $N$. Initially, all numbers are unmarked.

2. Starting from $p=2$, we will mark all multiples of $2$ less than or equal to $N$. These numbers are definitely not prime since $2$ divides them.

3. Move to the next unmarked number, i.e., $p = 3$. Mark all its multiples.

4. Stop if $p>\sqrt{N}$

Each unmarked number that we visit is a prime because all non-primes will be marked by one of its factors before we reach this number.

We can use a Boolean array of size $N$ to distinguish between marked and unmarked numbers.

Let’s understand the process better using the illustration below for $N = 30$. We will stop after we reach $ceil(\sqrt30)$ i.e $6$