Sieve of Eratosthenes

Picture writing every number from 2 to 30 on a whiteboard. Circle the first number still standing, 2, then cross out every multiple of it — 4, 6, 8, and so on. Those cannot be prime, since 2 divides them evenly. Move to the next number still standing, 3, circle it, cross out its multiples, and keep going. Whatever is still standing at the end, never crossed out, is a prime number — a number only divisible by 1 and itself.

1. 1Make a list of 'is it prime?' flags for every number from 0 up to n. Start them all as true, except for 0 and 1, which are not prime.
2. 2Starting at 2, if a number is still flagged as prime, cross out every multiple of it above itself.
3. 3Move to the next still-flagged number and repeat, up through the square root of n. Anything left flagged at the end is prime.

Use it to find all prime numbers up to some limit. It is much faster than testing each number one at a time. It is useful in cryptography, number theory problems, and building lookup tables of primes.

• ⚠Starting the crossing-out at i + i instead of i × i. Smaller multiples of i were already crossed out by smaller primes, so starting at i × i is a common speedup, though starting earlier still gives a correct, just slightly slower, result.
• ⚠Forgetting to mark 0 and 1 as not prime. The loop logic alone will not exclude them.