Počet dělitelů τ(n)

O(n log n)

Funkce τ(m) udává, kolik kladných celých čísel dělí m. Toto síto prochází d od 1 do n a pro každý násobek d zvyšuje čítač, čímž v čase O(n log n) nashromáždí celkový počet. Prvočísla mají přesně dva dělitele (1 a sebe) a jsou zelená; čísla s nejvíce děliteli v rozsahu jsou zvýrazněna zlatě. Tzv. vysoce složená čísla — ta s více děliteli než všechna menší čísla — vizuálně vynikají jako zlaté buňky.

Čísla
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Inicializace čítačů na 0 pro všechna m ve 2..n
  2. Pro každé d projdi násobky a zvyšuj τ[m]
  3. Klasifikace: prvočísla (τ=2) zeleně, nejvíce dělitelů zlatě
  4. Výpis maximálního počtu dělitelů

Pseudokód

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