У математици, Сундарамово сито је једноставан детерминистички алгоритам за проналажење свих простих бројеве до одређеног целог броја. Открио га је индијски математичар С. П. Сундарам 1934.године.
Алгоритам right|frame|Сундарамобо сито: кораци алгоритма за просте бројеве испод 202 (оптимално). Почиње са листом целих бројева од 1 до n. Из ове листе, уклања све бројеве у облику i + j + 2ij где:
Преостали бројеви се удвостручују, повећавају се, дајући листу непарним бројевима (тј простим, сви прости бројеви осим 2) испод 2n + 2.
Сито Сундарам сита од сложених бројева ради као Ератостеново сито, али чак се бројеви не сматрају; рад "прецртава" и више 2 врши последњи корак двоструког-краја-прираштаја. Кад год би се Ератостенова метода могла прецртати без к различитих простих бројева 2i+1, Сундарамова метода прецртава i + j(2i+1) for .
Исправности Ако почнемо са целим бројевима од 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
Литература
(translation of Russian book ) A new "sieve" for primes, an excerpt from
External link in |work= (help)
Спољашње везе A C99 implementation of the Sieve of Sundaram using bitarrays
Категорија:Тестови прималитета