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

В этой статье поговорим о нахождении простых чисел с помощью языка программирования C. Будем использовать алгоритм, который называется “Решето Эратосфена”.

В начале определение. Простое число – это такое натуральное число, которое делится само на себя и на единицу.

Дано натуральное число n, которое больше или равно двум (n>=2). Необходимо найти все простые числа, которые не больше n, то есть нужно найти все простые числа, принадлежащие отрезку [2; n]. Для поиска этих чисел будем использовать алгоритм “Решето Эратосфена”. Он заключается в следующем:

  1. Выпишем все числа от 2 до n.
  2. Первое простое число 2. Присвоим это значение переменной p.
  3. Зачеркнем все числа в списке кратные p.
  4. Найдем первое незачеркнутое число, которое больше p, и присвоим переменной p это число.
  5. Повторяем пункты 3 и 4 до тех пор, пока это возможно. Если для данного p нету кратных чисел в списке (ничего не зачеркнули), то вычисления также закончены.

Итак, на основе этого алгоритма пишем программу:

Прокомментируем код. Считываем число n (строка 11), проверяем больше ли оно или равно двум (строка 12), если это так, то выполняем поиск простых чисел, используя “Решето Эратосфена”, иначе – выводим сообщение об ошибке.

Переменная bool flag (строка 9) необходима для контроля – “зачеркивали” ли мы число для данного p.

Рассмотрим поиск простых чисел. Выделим память под массив с числами (строка 15) и заполним его (16-17). Перебираем числа (18-34), проверяя кратны ли они текущему p, если нашли такое число, то сдвигаем все стоящие справа от него числа на единицу влево, тем самым, затирая (“зачеркивая”) это число. Так проверяем все числа. Если для данного p ни одно число не было “зачеркнуто”, то работа программы завершена, все числа в массиве – простые. Освобождаем память (37).

Исходник программы можно скачать внизу страницы. Демонстрация работы программы:

Поиск простых чисел - 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="">