×

# Sieve of Eratosthenes

An algorithm for making tables of primes. Sequentially write down the integers from 2 to the highest number n you wish to include in the table. Cross out all numbers >2 which are divisible by 2 (every second number). Find the smallest remaining number >2. It is 3. So cross out all numbers >3 which are divisible by 3 (every third number). Find the smallest remaining number >3. It is 5. So cross out all numbers >5 which are divisible by 5 (every fifth number).

Continue until you have crossed out all numbers divisible by $$\left\lfloor \sqrt { n } \right\rfloor$$, where $$\left\lfloor x \right\rfloor$$ is the floor function. The numbers remaining are prime. This procedure is illustrated in the above diagram which sieves up to 50, and therefore crosses out composite numbers up to $$\left\lfloor \sqrt { 50 } \right\rfloor =7$$. If the procedure is then continued up to n, then the number of cross-outs gives the number of distinct prime factors of each number.

Note by Crazy Singh
2 years, 10 months ago