Поиск простых чисел. Решето Сундарама на Си

Рассмотрим один из алгоритмов поиска простых чисел, который называется: Решето Сундарама. Будет представлена реализация алгоритма на языке программирования Си, а также пример консольной программы, демонстрирующей работу алгоритма в действии.

Простое число – это число, которое делится само на себя и на единицу (простые числа: 2, 3, 5, 7, 11 и т.д.).

Решето Сундарама – это алгоритм для нахождения всех простых чисел до некоторого натурального числа N. Алгоритм был разработан индийским студентом С. П. Сундарамом в 1934 году.

Описание работы алгоритма:

Необходимо исключить из отрезка [1; N] все числа, которые представляются суммой вида:

Решето Сундарама. Исключить числа такого вида. vscode.ru

переменные sieveOfSundaram-ij пробегают все натуральные значения, для которых выполняется условие sieveOfSundaram-if, а именно индексы i и j меняются в пределах:

sieveOfSundaram-i      sieveOfSundaram-j

Каждое не исключенное число необходимо умножить на два и прибавить к нему единицу. В результате получится последовательность простых чисел в отрезке [3; 2N+1].

Ниже приведена реализация алгоритма Решето Сундарама на языке программирования Си. Функция Sundaram принимает в качестве аргумента целое число N.

Также представляем вашему вниманию пример консольной программы на языке Си, которая считывает с клавиатуры целое число N и выводит на экран список простых чисел в отрезке [2; 2N+1].

Демонстрация работы программы:

Поиск простых чисел. Решето Сундарама на Си - vscode.ru

Если вы хотите скачать исходник этой программы, то нажмите на кнопку ниже.

Скачать исходник

 

 

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

Поиск простых чисел. Решето Эратосфена на Си

Поиск простых чисел. Решето Сундарама на Си
5 (100%) 1 vote

Поделиться в соц. сетях:

Добавить комментарий

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

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">