Curiosities · Foundation · 9 min
A sieve for primes
Crossing off multiples turns a grid of candidates into a list of primes.
WHAT HAPPENS IF…Why can a sieve through 30 stop after processing 5?
Loading the mathematical model…
Every composite n has a factor at most √n, since two larger factors would multiply to more than n. After all prime factors up to √N have been processed, every remaining integer greater than 1 is prime. Multiples below p² were already removed by smaller prime factors.
A detail that matters
Before the sieve finishes, unmarked integers are only candidates.
Keep the connection going
More curiosities ↗