Squarefree sieve

O(n log log n)

A squarefree number has no repeated prime factor in its factorisation. This sieve first finds primes up to √n with Eratosthenes, then for each prime p marks every multiple of p² as non-squarefree. Numbers that survive all such markings are squarefree (shown green); the rest are tan. Squarefree numbers have density 6/π² ≈ 0.608, meaning roughly 60.8% of integers are squarefree. The Möbius function μ(n) equals zero exactly on the non-squarefree numbers.

Numbers
Edit the input and press Play

How it works

  1. Find primes up to √n with a basic sieve
  2. For each prime p, mark multiples of p² as non-squarefree
  3. Reveal unmarked numbers as squarefree
  4. Report squarefree count

Pseudocode

1squarefreeSieve(n):                 # O(n log log n)2  isSquareFree[2..n] = true3  primes = eratosthenes(floor(sqrt(n)))4  for p in primes:5    for m = p*p to n step p*p:6      isSquareFree[m] = false      # p^2 divides m7  return isSquareFree