The power of prime numbers in computing

Sieve of Eratosthenes

Now let’s flip things around a bit and look at how coding helps us handle and understand one of the classic problems of math: discovering primeness. An ancient algorithm was described by Eratosthenes, working in the 3rd century BC. The algorithm, now called the Sieve of Eratosthenesprovides a set of steps for finding all the primes for a given number.

The basic idea behind the algorithm is to take a number, nand through a series of passes, eliminate the non-prime numbers. What remains when you’re done is the set of primes you are after. There are many possible ways to refine this process, but the basic modern version of the sieve begins by taking 2 and noting it as prime, then finding all the even numbers up to nnoting them as not prime. Then, we move to 3 and perform the same thing for multiples of 3. Continuing on, we do the same for all the numbers up to nonly skipping those numbers we have already noted as non-prime.

This is a very ancient example of an algorithm, and a programmer’s ability to put it into an executable format is a superpower, for sure. Here is a version in JavaScript (from Wikipedia):