Lineární síto (NSF)

O(n)

Lineární síto vylepšuje Eratosthenovo tím, že každé složené číslo škrtne přesně jednou. Pro každé i od 2 do n: pokud i nemá přiřazeného nejmenšího prvočíselného dělitele (NSF), je to prvočíslo; poté se pro každé prvočíslo p (v pořadí, dokud p nepřekročí NSF[i]) označí součin i·p s NSF = p. Štítek buňky zobrazuje NSF každého složeného čísla, což umožňuje okamžitou faktorizaci libovolného čísla v rozsahu. Algoritmus dosahuje lineárního času O(n).

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

Jak to funguje

  1. Inicializace všech čísel jako kandidátů
  2. Každé neoznačené číslo identifikujeme jako prvočíslo
  3. Škrtáme i·p pro každé prvočíslo p ≤ NSF[i], zapisujeme NSF
  4. Výpis počtu prvočísel

Pseudokód

1linearSieve(n):                     # O(n)2  spf[2..n] = 0                     # smallest prime factor3  primes = []4  for i = 2 to n:5    if spf[i] == 0:                 # i is prime6      spf[i] = i7      primes.append(i)8    for p in primes:9      if p > spf[i] or i*p > n: break10      spf[i*p] = p                 # cross each composite once11  return primes, spf