A prime number is a number that can only be divided by 1 and itself without remainders. My father taught me that 1 is a “special number” which is neither a prime number nor a composite number. A classic computer programming task is to find all the prime numbers from 2 (the first prime) to 100. Usually, the code iteratively goes over the numbers and checks the primality of each number.

The Sieve of Eratosthenes, shown to me by my dad when I was 12, is a beautiful ancient algorithm that approaches this task from a different angle. My father wrote all the numbers from 2 to 100 on a piece of paper with his clear handwriting. He then crossed out all the numbers in steps of 2, with the exception of 2 itself (i.e., 4, 6, 8, 10, …). Next, he crossed out all the numbers in steps of 3, with the exception of 3 itself (i.e., 6, 9, 12, 15, …). Of course, some of these numbers were already crossed out by “2”. As 4 was already crossed out, he moved to 5, crossing out all the multiples of 5, with the exception of 5 itself, and so on.

Quickly, all the remaining numbers were primes since no smaller factor could eliminate them.

It’s Python time

sieve = [x for x in range(101)]        # originally all the numbers are candidates
sieve[1] = 0                           # 1 is not a prime number
for x in range(2,101):                 # go over all the numbers from 2 to 100
   for composite in range(2*x,101,x):  # keep the current candidate and eliminate its multiples...
      sieve[composite] = 0             # ... by setting them to 0
primes = [x for x in sieve if x != 0]  # select all the numbers which were not eliminated
print(primes)

Output

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

This program leverages one of Python’s most powerful syntax features – list comprehension. If you’re not already familiar with it yet, it’s a valuable tool to add to your coding toolbox. List comprehension enables concise creation of lists based on specific rules, condensing what might otherwise require several lines of code into a single expression.

In this example, ‘sieve’ represents the list [0, 1, 2, 3, 4, 5, …], while ‘primes’ is a filtered list derived from ‘sieve’. It contains the numbers that survive the elimination process, achieved through the elegant application of list comprehension.