Linear sieve (SPF)

O(n)

The linear sieve improves on Eratosthenes by ensuring each composite number is crossed out exactly once. For each i from 2 to n, if i has no assigned smallest-prime-factor it is prime; then for each known prime p (in order, stopping once p exceeds spf[i]) the product i·p is marked with smallest prime factor p. The sub label shows the SPF of each composite, enabling instant factorisation of any number in the range. The algorithm achieves a provably linear O(n) time bound.

Numbers
Edit the input and press Play

How it works

  1. Initialize all numbers as candidates
  2. Identify each unmarked number as prime
  3. Cross i·p for each prime p ≤ spf[i], recording SPF
  4. Report prime count

Pseudocode

1linearSieve(n):                     # O(n)2  spf[2..n] = 0                     # smallest prime factor3  primes = []4  for i = 2 to n:5    if spf[i] == 0:                 # i is prime6      spf[i] = i7      primes.append(i)8    for p in primes:9      if p > spf[i] or i*p > n: break10      spf[i*p] = p                 # cross each composite once11  return primes, spf