Sieve of Sundaram

O(n log n)

The Sieve of Sundaram, invented by S. P. Sundaram in 1934, works on the range 1..k where k=⌊(n-1)/2⌋. Any integer m in that range of the form i+j+2ij (with 1≤i≤j) is marked; the unmarked values give odd primes via 2m+1, and 2 is prepended manually. It is equivalent to Eratosthenes in effect but operates differently: rather than crossing out multiples of each prime, it identifies composite-generating index pairs algebraically. The algorithm runs in O(n log n) time.

Numbers
Edit the input and press Play

How it works

  1. Initialize grid 2..n as candidates
  2. Mark integers i+j+2ij as composite generators
  3. Reveal: unmarked m give prime 2m+1, prepend 2
  4. Report total prime count

Pseudocode

1sundaram(n):                        # O(n log n)2  k = floor((n - 1) / 2)3  marked[1..k] = false4  for i = 1 to k:5    for j = i to k:6      m = i + j + 2*i*j7      if m <= k: marked[m] = true   # 2m+1 will be composite8      else: break9  primes = [2]10  for m = 1 to k:11    if not marked[m]: primes.append(2*m + 1)12  return primes