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

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

Алгоритам

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

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

• $i,j\in \mathbb{N},1\le i\le j$
• $i+j+2ij\le n$

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

Сито Сундарам сита од сложених бројева ради као Ератостеново сито, али чак се бројеви не сматрају; рад "прецртава" и више 2 врши последњи корак двоструког-краја-прираштаја. Кад год би се Ератостенова метода могла прецртати без к различитих простих бројева 2i+1, Сундарамова метода прецртава i + j(2i+1) for $1\le j\le \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.

Види још

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

Литература

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book (translation of Russian book Шаблон:Cite book)
• A new "sieve" for primesШаблон:Мртва веза, an excerpt from
• Шаблон:Cite journal
• Шаблон:Cite conference
• Шаблон:Cite journalExternal link in |work= (help)

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

• A C99 implementation of the Sieve of Sundaram using bitarrays