Divisor count τ(n)

O(n log n)

The number-of-divisors function τ(m) counts how many positive integers divide m. This sieve sweeps d from 1 to n and increments a counter for every multiple of d, accumulating the count in O(n log n) time. Primes have exactly two divisors (1 and themselves) and are coloured green; the number(s) with the most divisors in the range are highlighted amber. The highly composite numbers — those with more divisors than any smaller number — stand out visually as the amber cells.

Numbers
Edit the input and press Play

How it works

  1. Initialize counters to 0 for all m in 2..n
  2. For each d sweep its multiples, incrementing τ[m]
  3. Classify: primes (τ=2) green, most-divisors amber
  4. Report maximum divisor count found

Pseudocode

1divisorCount(n):                    # O(n log n)2  tau[1..n] = 03  for d = 1 to n:4    for m = d to n step d:5      tau[m] += 1                  # d is a divisor of m6  maxTau = max(tau[2..n])7  for m = 2 to n:8    if tau[m] == 2: mark prime9    elif tau[m] == maxTau: mark highlight10  return tau