The Sieve of Eratosthenes

Given an integer N > 1, you want to find all of the prime numbers from 1 to N. For example, if N = 11, then you get {2, 3, 5, 7, 11}.

The Sieve of Eratosthenes is a simple way to solve this problem. The basic idea behind it is this: Construct the list of all integers from 1 to N, and remove the composite numbers.

It is easy to construct the list of all integers from 1 to N. So, the question is: How do you remove the composite numbers?

Every composite number k has a prime factor that is less than or equal to sqrt(k). To see this, consider any composite number k = m * n. If both m > sqrt(k) and n > sqrt(k), then k < m * n. But k = m * n. So, k must have a prime factor that is less than or equal to sqrt(k).

So, we iterate to sqrt(N). Initially, each integer is marked as a prime. When we visit an integer, we unmark all of its multiples. In this way we remove all of the composite numbers. The prime numbers are the numbers that remain.

I implemented the Sieve of Eratosthenes in C, and I implemented the Sieve of Eratosthenes in Python.

Both of my implementations are up at my GitHub.