Eulerova funkce φ (síto)

O(n log log n)

Eulerova funkce φ(n) je počet čísel v 1..n nesoudělných s n — základní stavební kámen modulární aritmetiky a RSA. Místo testování každého čísla je síto spočítá všechna naráz. Začni s φ[i] = i. Procházej i zdola; první i, které je dosud rovné své počáteční hodnotě, musí být prvočíslo, takže na každý jeho násobek aplikuj φ ← φ·(1 − 1/i). Po zpracování všech prvočísel ≤ n je každé φ[m] součin (1 − 1/p) přes jeho prvočíselné dělitele p — přesně totient. Běží v O(n log log n), stejně jako prvočíselné síto, které napodobuje. Prvočísla svítí zeleně (φ(p) = p − 1) a malé číslo v každé buňce je jeho aktuální φ.

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

Jak to funguje

  1. Nastav φ[i] = i pro každé i.
  2. Procházej zdola; dosud nedotčené i je prvočíslo.
  3. Pro každý násobek m toho prvočísla vynásob φ[m] faktorem (1 − 1/p).
  4. Po dokončení průchodu jsou všechna φ konečná.

Pseudokód

1totientSieve(n):                    # O(n log log n)2  phi[i] ← i  for all i3  for i from 2 to n:4    if phi[i] = i:                   # i is prime5      for m from i to n step i:6        phi[m] ← phi[m] − phi[m]/i   # apply (1 − 1/i)7  return phi