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

В математике , то решето Сундарама простой детерминированный алгоритм для нахождения всех простых чисел до заданного целого числа. Он был открыт индийским математиком С.П. Сундарамом в 1934 году. ^{[1] [2]}

Алгоритм [ править ]

Сито Сундарама: шаги алгоритма для простых чисел меньше 202 (неоптимизировано).

Начните со списка целых чисел от 1 до n . Из этого списка удалите все числа вида i + j + 2 ij, где:

• ${\ Displaystyle I, J \ in \ mathbb {N}, \ 1 \ Leq I \ Leq J}$
• ${\ Displaystyle я + J + 2ij \ Leq п}$

Остальные числа удваиваются и увеличиваются на единицу, давая список нечетных простых чисел (т. Е. Всех простых чисел, кроме 2) ниже 2 n + 1 .

Сито Сундарама отсеивает составные числа так же, как сито Эратосфена , но четные числа не учитываются; работа по «вычеркиванию» числа, кратного 2, выполняется последним шагом «двойное и приращение». Всякий раз , когда метод Эратосфена будет зачеркивать K различных кратного штриха , метод сундаров в перечеркивает для .${\ displaystyle 2i + 1}$${\ Displaystyle я + J (2i + 1)}$${\ Displaystyle 1 \ Leq J \ Leq \ lfloor k / 2 \ rfloor}$

Правильность [ править ]

Если мы начнем с целых чисел от 1 до n , окончательный список будет содержать только нечетные целые числа от 3 до . Из этого окончательного списка были исключены некоторые нечетные целые числа; мы должны показать, что это в точности составные нечетные целые числа меньше чем .${\ displaystyle 2n + 1}$${\ displaystyle 2n + 2}$

Пусть q - нечетное целое число вида . Тогда q исключается тогда и только тогда, когда k имеет вид , то есть . Тогда у нас есть:${\ displaystyle 2k + 1}$ ${\ displaystyle i + j + 2ij}$${\ Displaystyle д = 2 (я + J + 2ij) +1}$

${\ displaystyle {\ begin {align} q & = 2 (i + j + 2ij) +1 \\ & = 2i + 2j + 4ij + 1 \\ & = (2i + 1) (2j + 1). \ end { выровнено}}}$

Таким образом, нечетное целое число исключается из окончательного списка тогда и только тогда, когда оно имеет факторизацию формы, то есть, если оно имеет нетривиальный нечетный множитель. Следовательно, список должен состоять из набора нечетных простых чисел, меньших или равных .${\ Displaystyle (2i + 1) (2j + 1)}$${\ displaystyle 2n + 2}$

def  sieve_of_Sundaram ( n ):  "" "Решето Сундарама - это простой детерминированный алгоритм для поиска всех простых чисел вплоть до указанного целого числа." ""  k  =  ( n  -  2 )  //  2  integer_list  =  [ True ]  *  ( k  +  1 )  для  i  в  диапазоне ( 1 ,  k  +  1 ):  j  =  i,  а  i  +  j  +  2  *  i  * j  <=  k :  inteers_list [ i  +  j  +  2  *  i  *  j ]  =  False  j  + =  1,  если  n  >  2 :  print ( 2 ,  end = '' )  для  i  в  диапазоне ( 1 ,  k  +  1 ):  if  список_целых [ i ]:  print ( 2  *  i  +  1,  конец = '' )

См. Также [ править ]

• Сито Эратосфена
• Сито Аткина
• Теория сита

Ссылки [ править ]

• Огилви, К. Стэнли ; Джон Т. Андерсон (1988). Экскурсии по теории чисел . Dover Publications , 1988 (перепечатка из Oxford University Press , 1966). С. 98–100, 158. ISBN 0-486-25778-9.
• Хонсбергер, Росс (1970). Изобретательность в математике . Новая математическая библиотека №23. Математическая ассоциация Америки . С.  75 . ISBN 0-394-70923-3.
• Новое «решето» для простых чисел ^{[ постоянная мертвая ссылка ]} , отрывок из Кордемского, Борис А. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung . MSB Nr. 78. Urania Verlag. п. 200.(перевод русской книги Кордемский, Борис Анастасьевич (1958). Математическая смекалка . М .: ГИФМЛ.)
• Мовшовиц-Хадар, Н. (1988). «Стимулирующие представления теорем, за которыми следуют отзывчивые доказательства». Для изучения математики . 8 (2): 12–19.
• Феррандо, Элизабетта (2005). Отводящие процессы в предположениях и доказательствах (PDF) (PhD). Университет Пердью. С. 70–72.
• Бакстер, Эндрю. «Сито Сундарама» . Темы из истории криптографии . Математический факультет МУ.

Внешние ссылки [ править ]

• Реализация решета Сундарама на C99 с использованием битовых массивов