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

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

Алгоритам

Сундарамобо сито: кораци алгоритма за просте бројеве испод 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.

Види још

• Ератостеново сито
• Аткиново сито
• Теорија сита

Литература

• 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