Eratosthenovo síto

O(n log log n)

Eratosthenovo síto najde všechna prvočísla do n, aniž by u jakéhokoli čísla testovalo prvočíselnost. Vypiš 2, 3, …, n. První neškrtnuté číslo, 2, je prvočíslo — vyškrtej každý jeho násobek. Další neškrtnuté, 3, je prvočíslo — vyškrtej jeho násobky. Pokračuj; pokaždé další stojící číslo musí být prvočíslo, protože ho nedělí nic menšího. Stačí prosévat do √n (složené číslo ≤ n má dělitele ≤ √n) a každé prvočíslo p můžeš začít škrtat od p², protože menší násobky už byly škrtnuté. Běží v O(n log log n) — skoro lineárně. Prvočísla zůstanou zelená, složená jsou přeškrtnutá a právě prosévané prvočíslo má kroužek.

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

Jak to funguje

  1. Vypiš každé číslo od 2 do n jako kandidáta.
  2. Vezmi nejmenší dosud neškrtnuté číslo — je to prvočíslo.
  3. Vyškrtej všechny jeho násobky (počínaje jeho druhou mocninou).
  4. Opakuj do √n; vše dosud neškrtnuté je prvočíslo.

Pseudokód

1sieve(n):                           # O(n log log n)2  mark 2..n as candidate primes3  for p from 2 while p·p ≤ n:4    if p is still uncrossed (prime):5      cross out p·p, p·p+p, p·p+2p, … up to n6  every still-uncrossed number is prime