Сундарамово сито

У математици, Сундарамово сито је једноставан детерминистички алгоритам за проналажење свих простих бројеве до одређеног целог броја. Открио га је индијски математичар С. П. Сундарам 1934.године.^[1]^[2]

Алгоритам

Сундарамобо сито: кораци алгоритма за просте бројеве испод 202 (оптимално).

Почиње са листом целих бројева од 1 до n. Из ове листе, уклања све бројеве у облику i j 2ij где:

$i,j\in \mathbb {N} ,\ 1\leq i\leq j$
$i j 2ij\leq n$

Преостали бројеви се удвостручују, повећавају се, дајући листу непарним бројевима (тј простим, сви прости бројеви осим 2) испод 2n 2.

Сито Сундарам сита од сложених бројева ради као Ератостеново сито, али чак се бројеви не сматрају; рад "прецртава" и више 2 врши последњи корак двоструког-краја-прираштаја. Кад год би се Ератостенова метода могла прецртати без к различитих простих бројева 2i 1, Сундарамова метода прецртава i j(2i 1) for $1\leq j\leq \lfloor k/2\rfloor$ .

Исправности

Ако почнемо са целим бројевима од 1 до n, коначна листа садржи само непарне целе бројеве од 3 до 2n 1. Из овог коначног списка, неки непарни цели бројеви су искључени: морамо показати управо то су сложени непарни цели бројеви мањи од 2n 2.

Пустити q да буде непаран цео број од 2k 1. Тада, q је искључен ако и само ако k је од i j 2ij, тада је q = 2(i j 2ij) 1. Онда имамо:

q = 2(i j 2ij) 1

= 2i 2j 4ij 1

= (2i 1)(2j 1).

Дакле, непаран цео број је искључен из коначне листе ако и само ако има разлагања облика (2i 1)(2j 1) — што ће рећи, ако има нетривијални непарни фактор. Стога листа мора чинити управо скуп непарних простих бројева мањих или једнаких од 2n 2.

Види још

Reference

^ V. Ramaswami Aiyar (1934). „Sundaram's Sieve for Prime Numbers”. The Mathematics Student. 2 (2): 73. ISSN 0025-5742.
^ G. (1941). „Curiosa 81. A New Sieve for Prime Numbers”. Scripta Mathematica. 8 (3): 164.

Литература

Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from Oxford University Press, 1966). стр. 98—100,158. ISBN 978-0-486-25778-5.
Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. стр. 75. ISBN 978-0-394-70923-9.
Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. стр. 200. (translation of Russian book Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ. Архивирано из оригинала 16. 10. 2019. г. Приступљено 14. 11. 2015. )
A new "sieve" for primes^{[мртва веза]}, an excerpt from
Movshovitz-Hadar, N. (1988). „Stimulating Presentations of Theorems Followed by Responsive Proofs”. For the Learning of Mathematics. 8 (2): 12—19.
Ferrando, Elisabetta (2005). „Abductive processes in conjecturing and proving” (PDF). Ph.D. theses. Purdue University. стр. 70—72. Архивирано из оригинала (PDF) 07. 05. 2016. г. Приступљено 14. 11. 2015.
Baxter, Andrew. „Sundaram’s Sieve”. Topics from the History of Cryptography. MU Department of Mathematics. Архивирано из оригинала 12. 08. 2011. г. Приступљено 14. 11. 2015. External link in |work= (help)

Спољашње везе

A C99 implementation of the Sieve of Sundaram using bitarrays

[1] V. Ramaswami Aiyar (1934). „Sundaram's Sieve for Prime Numbers”. The Mathematics Student. 2 (2): 73. ISSN 0025-5742.

[2] G. (1941). „Curiosa 81. A New Sieve for Prime Numbers”. Scripta Mathematica. 8 (3): 164.

[1]

[2]