Sieve of Eratosthenes

Sieve of Eratosthenes

The Greek mathematician Eratosthenes found primes without dividing anything: write down the numbers, then cross out the multiples of each prime.

[True] * (n + 1) makes a list of n + 1 True values, one for each number from 0 to n. Mark 0 and 1 as not prime. Then, for each p still marked True, set every multiple of p from p * p onwards to False. The numbers still marked True at the end are the primes.