I was rummaging around in some old directories and found an implementation of the Sieve of Eratosthenes that I’d thought I’d share. I thought I’d share it because of the simplicity of the algorithm, it represented a very enjoyable programming exercise and one that I now use as a standard kata when learning a new language. The Sieve of Eratosthenes is an algorithm used to identify prime numbers.
In it’s simplest form, the algorithm states:
set Array to array of size N set Array to all true for i from 2 to N for each j where i divides j, j from i + 1 to N set Array(j) to false
Basically, it trawls an array of “on” bits and “turns off” any index that is cleanly divisible by any number less than the square root of it’s size.