Решето Сундарама.

Решето Сундарама – алгоритм поиска всех простых чисел в некотором заданном диапазоне. Он был разработан в 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.

Код программы на C++:

Код программы на Pascal:

 


Похожие записи:

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля отмечены *