8.3. Простые числа

1. Число 1 имеет только один положительный делитель, именно 1. В этом отношении число 1 в ряде натуральных чисел стоит совершенно особо.

Всякое целое, большее 1, имеет не менее двух делителей, именно 1 и самого себя; если других делителей нет, то число называется простым. Целое, большее 1, имеющее кроме 1 и самого себя другие положительные делители, называют составным.

2. Наименьший отличный от единицы делитель целого, большего единицы, есть число простое. В противном случае, можно было бы выбрать делитель еще меньше.

3. Наименьший отличный от единицы делитель (он будет простым) составного числа не превосходит . Действительно, пусть именно этот делитель, тогда наименьший делитель), откуда или

4. Простых чисел бесконечно много. Это следует из того, что каковы бы ни были различные простые числа можно получить новое простое, среди них не находящееся. Таковым будет простой делитель суммы который, деля всю сумму, не может совпадать ни с одним из простых

5. Решето Эратосфена для составления таблицы простых чисел. Данный способ состоит в следующем.

Выписываем числа

Первое, большее 1, число этого ряда есть 2. Оно делится только на себя и на 1 и, следовательно, оно простое. Вычеркиваем из ряда (как составные) все числа, кратные 2, кроме самого себя. Первое, следующее за 2 не вычеркнутое число есть 3 — оно также будет простым. С ним, как и с числом 2, проделываем ту же процедуру и т.д. Если указанным способом уже вычеркнуты все числа кратные простых, меньших то все невычеркнутые, меньшие будут простые.

Составление таблицы простых чисел, не превосходящих закончено, как только вычеркнуты все составные кратные простых, не превосходящих

В алгоритме 8.1 реализовано решето Эратосфена для нечетных чисел с предпросеиванием для двойки; другими словами, начинаем только с нечетных чисел, отсеивая кратные 3, 5, 7, 11 и т.д. Вектор Хявляется двоичным набором индикаторов простых нечетных чисел. Так элемент вектора если соответствующее ему число простое; в противном случае, когда число непростое.

Алгоритм 8.1. Решето Эратосфена

(см. скан)

(см. скан)

Алгоритм 8.3. Программа на Си генерации простых чисел

(см. скан)

Исходными данными для программ алгоритмов 8.2 и 8.3 является верхняя граница диапазона поиска простых чисел. Значение этой границы устанавливается явным образом в программе посредством присваивания соответствующего значения переменной Нижняя граница диапазона всегда принимается равной 3 — первое нечетное простое число.

Результаты расчетов по программам алгоритмов 8.2 и 8.3 сохраняются в выходном файле со следующей структурой:

В первой строке приводятся все вычисленные простые нечетные числа из диапазона границы которого распечатываются во второй строке результирующего файла. Во второй же строке указывается и общее количество найденных простых чисел.