Сито Сундарама - Sieve of Sundaram

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

Алгоритм

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

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

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

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

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

Правильность

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

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

${\displaystyle {\begin{aligned}q&=2(i+j+2ij)+1\\&=2i+2j+4ij+1\\&=(2i+1)(2j+1).\end{aligned}}}$

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

def sieve_of_Sundaram(п):    "" "Решето Сундарама - это простой детерминированный алгоритм для поиска всех простых чисел до указанного целого числа." ""    k = (п - 2) // 2    целые_список = [Истинный] * (k + 1)    за я в классифицировать(1, k + 1):        j = я        пока я + j + 2 * я * j <= k:            целые_список[я + j + 2 * я * j] = Ложь            j += 1    если п > 2:        Распечатать(2, конец=' ')    за я в классифицировать(1, k + 1):        если целые_список[я]:            Распечатать(2 * я + 1, конец=' ')

Смотрите также

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

Рекомендации

1. В. Рамасвами Айяр (1934). «Сито Сундарама для простых чисел». Студент-математик. 2 (2): 73. ISSN  0025-5742.
2. Г. (1941). «Куриоза 81. Новое сито для простых чисел». Scripta Mathematica. 8 (3): 164.

• Огилви, К. Стэнли; Джон Т. Андерсон (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) (Кандидат наук). Университет Пердью. С. 70–72.
• Бакстер, Эндрю. "Сито Сундарама". Темы из истории криптографии. Математический факультет МУ.

внешняя ссылка

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