Sieve μ(1..n): O(n)
Single μ(n): O(√n)
Coprime count: O(n) / O(√n) blocked
Identity: μ * 1 = ε
Linear Sieve of the Möbius Function
μ = +1 (even #primes)
μ = −1 (odd #primes)
μ = 0 (not squarefree)
current
Step Explanation
Press Play to run the linear sieve, or Step to advance one operation.
Live Facts
step0 / 0
modesieve
n12
running total—
cross-check—
Complexity
| Operation | Time |
|---|
| μ(n), one value (factor) | O(√n) |
| μ(1..n) linear sieve | O(n) |
| μ(1..n) Eratosthenes | O(n log log n) |
| Inversion at one n | O(d(n)) |
| Coprime count Σμ(d)⌊n/d⌋² | O(n) |
| Coprime count (divisor blocks) | O(√n) |
| Sublinear Mertens M(x) | O(n^2/3) |