Sundaramovo síto

O(n log n)

Sundaramovo síto, které vymyslel S. P. Sundaram v roce 1934, pracuje s rozsahem 1..k, kde k=⌊(n-1)/2⌋. Každé celé číslo m v tomto rozsahu tvaru i+j+2ij (pro 1≤i≤j) se označí; neoznačené hodnoty dávají lichá prvočísla vzorcem 2m+1 a ručně se přidá číslo 2. Algoritmus je ekvivalentní Eratosthenově sítu co do výsledku, ale pracuje jinak — namísto škrtání násobků každého prvočísla algebraicky identifikuje indexové páry generující složeniny. Složitost je O(n log n).

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

Jak to funguje

  1. Inicializace mřížky 2..n jako kandidátů
  2. Označení celých čísel i+j+2ij jako generátorů složenin
  3. Odhalení: neoznačená m dávají prvočíslo 2m+1, přidá se 2
  4. Výpis celkového počtu prvočísel

Pseudokód

1sundaram(n):                        # O(n log n)2  k = floor((n - 1) / 2)3  marked[1..k] = false4  for i = 1 to k:5    for j = i to k:6      m = i + j + 2*i*j7      if m <= k: marked[m] = true   # 2m+1 will be composite8      else: break9  primes = [2]10  for m = 1 to k:11    if not marked[m]: primes.append(2*m + 1)12  return primes