Sieve of Eratosthenes

O(n log log n)

The Sieve of Eratosthenes finds all primes up to n without ever testing a number for primality. Write out 2, 3, …, n. The first uncrossed number, 2, is prime — cross out every multiple of it. The next uncrossed number, 3, is prime — cross out its multiples. Keep going; each time, the next number still standing must be prime, because nothing smaller divides it. You only need to sieve up to √n (a composite ≤ n has a factor ≤ √n), and you can start crossing each prime p from p² since smaller multiples were already struck. It runs in O(n log log n) — almost linear. Primes stay green, composites are struck through, and the prime currently sieving is ringed.

Numbers
Edit the input and press Play

How it works

  1. Write every number from 2 to n as a candidate.
  2. Take the smallest number not yet crossed — it is prime.
  3. Cross out all of its multiples (starting from its square).
  4. Repeat up to √n; everything still uncrossed is prime.

Pseudocode

1sieve(n):                           # O(n log log n)2  mark 2..n as candidate primes3  for p from 2 while p·p ≤ n:4    if p is still uncrossed (prime):5      cross out p·p, p·p+p, p·p+2p, … up to n6  every still-uncrossed number is prime