Лекция
Привет, сегодня поговорим про решето сундарама, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое решето сундарама , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
решето сундарама – это алгоритм поиска всех простых чисел в некотором заданном диапазоне. Он был разработан в 1934 году ныне безызвестным студентом из Индии С. П. Сундарамом.
Принцип работы алгоритма Сундарама сводится, как и в его знаменитом предшественнике, к последовательному отсеиванию всех ненужных чисел. Но у него есть одна небольшая особенность: результатом работы алгоритма будет последовательность простых чисел из диапазона от 2 до удвоенного значения граничного числа. Допустим необходимо получить все простые числа до некоторого N, тогда выходными данными будут все простые числа от 2 до 2N+1.
Решето Сундарама из ряда натуральных чисел, не превышающих N, исключает числа вида 2ij+i+j. Результат данного выражения, ни при каких значениях входящих в него переменных, не превышает N (2ij+i+j≤N). Соблюдая это условие, а также то, что i всегда меньше или равно j, переменные i и j пробегают все натуральные значения из множеств:
После исключения всех ненужных чисел необходимо увеличить каждое оставшиеся число в два раза и прибавить единицу (2i+1). Итоговое множество будет содержать числа: 2, 3, …, 2N+1.
Решето Сундара́ма — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа 
. Разработан индийским студентом Сундарамом в 1934 году.
Алгоритм предусматривает исключение из ряда натуральных чисел от 1 до }
всех чисел вида:
,
где индексы 
пробегают все натуральные значения, для которых 
, а именно значения 
и 
Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Об этом говорит сайт https://intellect.icu . Полученная в результате последовательность представляет собой все простые числа в отрезке 
.
Алгоритм работает с нечетными натуральными числами большими единицы, представленными в виде 
, где 
является натуральным числом.
Если число является составным, то по определению оно может быть представлено в виде произведения двух нечетных чисел, больших единицы, то есть:
, где 
и 
— натуральные числа. Раскрывая скобки, получаем, что
, или
, из чего следует, что
.
Таким образом, если из ряда натуральных чисел исключить все числа вида 
( 
), то для каждого из оставшихся чисел } число обязано быть простым. И, наоборот, если число является простым, то число {\displaystyle m} невозможно представить в виде и, таким образом, не будет исключено в процессе работы алгоритма.
На этом все! Теперь вы знаете все про решето сундарама, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое решето сундарама и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Из статьи мы узнали кратко, но содержательно про решето сундарама
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов