Síto Sundaram - Sieve of Sundaram

v matematika, síto Sundaram je jednoduchý deterministický algoritmus za nalezení všech prvočísla až do zadaného celého čísla. Objevil jej indický matematik pan S. P. Sundaram v roce 1934.^[1][2]

Algoritmus

Sieve of Sundaram: kroky algoritmu pro prvočísla pod 202 (neoptimalizované).

Začněte seznamem celých čísel od 1 do n. Z tohoto seznamu odeberte všechna čísla formuláře i + j + 2ij kde:

• ${ displaystyle i, j in mathbb {N}, 1 leq i leq j}$
• ${ displaystyle i + j + 2ij leq n}$

Zbývající čísla jsou zdvojnásobena a zvýšena o jednu, čímž je uveden seznam lichých prvočísel (tj. Všech prvočísel kromě 2) níže 2n + 1.

Síto Sundaram stejně rozděluje složená čísla síto Eratosthenes ano, ale ani čísla nejsou zohledněna; práce na „přeškrtnutí“ násobků 2 se provede závěrečným krokem zdvojnásobení a zvýšení. Kdykoli by se Eratosthenova metoda přeškrtla k různé násobky prvočísla ${ displaystyle 2i + 1}$Sundaramova metoda přeškrtne ${ displaystyle i + j (2i + 1)}$ pro ${ Displaystyle 1 leq j leq lfloor k / 2 rfloor}$.

Správnost

Pokud začneme s celými čísly od 1 na n, konečný seznam obsahuje pouze lichá celá čísla z 3 na ${ displaystyle 2n + 1}$. Z tohoto konečného seznamu byla vyloučena některá lichá celá čísla; musíme ukázat, že se jedná přesně o kompozitní lichá celá čísla menší než ${ displaystyle 2n + 2}$.

Nechat q být liché celé číslo formuláře ${ displaystyle 2k + 1}$. Pak, q je vyloučeno kdyby a jen kdyby k je ve formě ${ displaystyle i + j + 2ij}$, to je ${ displaystyle q = 2 (i + j + 2ij) +1}$. Pak máme:

${ displaystyle { begin {sladěno} q & = 2 (i + j + 2ij) +1 & = 2i + 2j + 4ij + 1 & = (2i + 1) (2j + 1). end { zarovnaný}}}$

Takže liché celé číslo je vyloučeno z konečného seznamu právě tehdy, pokud má faktorizaci formuláře ${ displaystyle (2i + 1) (2j + 1)}$ - což znamená, že má netriviální lichý faktor. Seznam tedy musí být složen přesně z množiny lichých primární čísla menší nebo rovna ${ displaystyle 2n + 2}$.

def sieve_of_Sundaram(n):    "" "Sundaramské síto je jednoduchý deterministický algoritmus pro vyhledání všech prvočísel až po zadané celé číslo." ""    k = (n - 2) // 2    integers_list = [Skutečný] * (k + 1)    pro i v rozsah(1, k + 1):        j = i        zatímco i + j + 2 * i * j <= k:            integers_list[i + j + 2 * i * j] = Nepravdivé            j += 1    -li n > 2:        tisk(2, konec=' ')    pro i v rozsah(1, k + 1):        -li integers_list[i]:            tisk(2 * i + 1, konec=' ')

Viz také

• Síto Eratosthenes
• Síto z Atkinu
• Teorie síta

Reference

• Ogilvy, C. Stanley; John T. Anderson (1988). Exkurze v teorii čísel. Dover Publications, 1988 (dotisk z Oxford University Press, 1966). 98–100, 158. ISBN  0-486-25778-9.
• Honsberger, Ross (1970). Vynalézavost v matematice. Nová matematická knihovna č. 23. Mathematical Association of America. str.75. ISBN  0-394-70923-3.
• Nové „síto“ pro prvočísla^{[trvalý mrtvý odkaz ]}, výňatek z Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB č. 78. Urania Verlag. p. 200. (překlad ruské knihy Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М .: ГИФМЛ.)
• Movshovitz-Hadar, N. (1988). "Stimulace prezentace vět následovaných responzivními důkazy". Pro učení matematiky. 8 (2): 12–19.
• Ferrando, Elisabetta (2005). Únosové procesy při dohadování a dokazování (PDF) (PhD). Purdue University. 70–72.
• Baxter, Andrew. „Sundaramovo síto“. Témata z dějin kryptografie. Katedra matematiky MU.

externí odkazy

• C99 implementace Sieve of Sundaram pomocí bitarrays