Linear Sieve (Euler's Sieve) & Multiplicative Functions

Each composite is marked exactly once by its smallest prime factor — filling spf, φ, and μ in O(n).

Time O(n) Space O(n) Each composite marked once
prime
current i
marking (coprime: p ∤ i)
marking (square: p | i, then break)

Number grid — spf / φ / μ

What's happening

Press Start to run the linear sieve, or Step for one operation at a time.

Live stats

current i-
primes found0
composites marked0
expected n - π(n)-
coprime marks0
square marks0
step0 / 0

Complexity

OperationCost
Build spf, φ, μO(n)
Factor x ≤ nO(log x)
Query φ(x) / μ(x)O(1)
Eratosthenes (compare)O(n log log n)
Space (int tables)O(n)

Operation log