Dělitelé čísla n

O(n)

Tento jednoduchý O(n) algoritmus testuje každé celé číslo d od 1 do n, zda n mod d se rovná nule. Každý dělitel je zvýrazněn zeleně a každý nedělitel je obarven hnědě, přičemž aktuální kandidát je označen oranžovým kroužkem. Ačkoli existuje optimalizace odmocninou, celý průchod je zde záměrný: přímo demonstruje definici dělitelnosti a v mřížce zviditelňuje symetrii dělitelů (pokud d dělí n, pak n/d také dělí n). Událost done hlásí celý seznam dělitelů a τ(n).

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

Jak to funguje

  1. Inicializace mřížky 1..n jako kandidátů
  2. Testuj každé d: pokud n mod d = 0 zeleně, jinak hnědě
  3. Posouvej oranžový kroužek s každým testovaným d
  4. Výpis seznamu dělitelů a celkového počtu

Pseudokód

1divisorsOf(n):                      # O(n)2  divisors = []3  for d = 1 to n:4    if n mod d == 0:5      divisors.append(d)           # d divides n6  return divisors                  # tau(n) = len(divisors)