Rozklad na prvočísla (faktorizační strom)

O(√n) per factor

Každé celé číslo větší než 1 se jednoznačně rozkládá na prvočísla — základní věta aritmetiky — a faktorizační strom tento rozklad ukazuje větev po větvi. Vezmi aktuální číslo, odlup jeho nejmenší prvočíselný dělitel jako list a kofaktor nech dál se štěpit napravo. Když je uzel sám prvočíslo, stane se listem a strom se zastaví. Čtení listů zleva doprava dává prvočíselný rozklad. Hledání každého nejmenšího dělitele zkusmým dělením stojí O(√n), proto je rozklad velkých čísel těžký — bezpečnost RSA stojí přesně na této obtížnosti. Levý potomek při každém štěpení je prvočíslo; pravý potomek je to, co zbývá rozložit.

Binární vyhledávací strom
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Najdi nejmenší prvočíselný dělitel p aktuálního čísla.
  2. Rozděl ho na p (list) a n/p.
  3. Pokračuj rekurzivně na n/p.
  4. Skonči, když je zbývající číslo prvočíslo.

Pseudokód

1factorTree(n):                      # O(√n) per factor2  p ← smallest prime factor of n3  if p = n:  return leaf(n)          # n is prime4  return node(n, leaf(p), factorTree(n / p))