Предыдущий раздел

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

     Изучается гипотеза, что все нечетные числа, большие 2, – простые.
   Математик: 3 – простое, 5 – простое, 7 – простое, 9 – не простое. Это контрпример. Гипотеза неверна.
   Физик: 3 – простое, 5 – простое, 7 – простое, 9 – ой!, 11 – простое, 13 – простое. Достаточно... Возвращаясь к числу 9, я заключаю, что это была ошибка эксперимента.
   Инженер: Возьмем наугад: 7 – простое, 13 – простое, 27 – простое... Вот, все простые.
   Программер: Напишем тестирующую программу. Она выдает: 1 – простое, 1 – простое, 1 – простое, 1 – простое... Да все они простые!

  Задача 1. Дано натуральное число n, выяснить, простое ли оно.

Что значит, что n – простое? А вот что: на какое бы натуральное число i > 1 мы не делили число n, кроме 1 и n, оно нацело не поделится. Значение 1 исключается, так как на него делятся все числа. Разумеется, надо ограничить диапазон проверяемых значений i и сверху.

Немного математики. Конечно, не стоит проверять делимость числа n на делители, большие, чем n / 2. Если бы там были интересующие нас делители, то дополнительными делителями были бы числа n / i < 2, а они не целые!
Пойдем дальше. Будем проверять делимость на числа i в порядке возрастания значений i. Пусть и является делителем числа n, тогда целым делителем должно быть и число . Таким образом, множитель n / i будет обнаружен никак не позже, чем i, и поэтому множитель i проверять уже не надо.
Итак, надо проверить, делится ли n на числа i, принимающие все значения от 2 до (что означает целую часть числа , которое может оказаться дробным, и во всяком случае значение функции Sqrt(n) имеет действительный, а не целый тип. На Pascal это выражается так: m := Trunc(Sqrt(n))).
 
Таким образом,

число n простое <=> n не делится на 2 и n не делится на 3 и ... и n не делится на m.

Получается фрагмент программы, содержащий цикл по индексу i. Для вычисления логической величины – ответа – надо операцию "логическое и" выполнить над последовательностью логических значений "n не делится на 2", "n не делится на 3", и т.д. Для последовательного выполнения этих операций заведем логическую переменную-накопитель lval.
 

Конечно, это еще не рабочая программа. Чтобы она заработала, надо перевести выделенное красным цветом на язык Pascal. Но прежде, чем это делать, задумаемся вот над чем.

1. Уж если мы обнаружили делитель числа n, то зачем проверять делимость n на другие значения i ? Надо сразу прекратить выполнение цикла:
 

2. Наше сочинение только тогда будет представлять самостоятельную ценность, когда им можно пользоваться не только для выяснения простоты введенного с клавиатуры числа, а и в каком-нибуль сложном вычислительном процессе для проверки многих возникающих в счете чисел. Поэтому перепишем еще раз строки программы, организовав их теперь в виде функции:
 

Для окончательной отделки осталось перевести на Pascal выделенное красным. Для этого используем операцию n MOD i – частное от деления n на i. Если оно равно 0, то делимость есть. От программирования ввода числа n и вывода результата мы избавились, переложив эти проблемы на того, кто будет пользоваться нашей функцией. Еще одно усовершенствование заключается в использовании имени функции вместо вспомогательной локальной переменной lval. Таким образом, от вспомогательной логической переменной–накопителя не осталось и следа! Окончательно получаем следующий текст функции:
 

Если эта функция представляет для вас интерес, можете принять содержащий ее файл simple.pas.

  Задача 2. Дано натуральное число n.
а) Вывести на экран все его простые множители, причем каждый из них столько раз, сколько раз оно входит в разложение числа n на простые множители.
б) Заполнить найденными делителями заданный массив.
в) Проверить, является ли оно совершенным числом (напомню, что совершенным называют такое натуральное число, сумма всех делителей которого, исключая его самого, равна этому числу). Надо ли для этого использовать полученный в пункте б) массив? Как лучше завершать выполнение цикла ?

Решето Эратосфена

Этот древний грек (3 век до н.э.) придумал способ получения всех простых чисел, не превосходящих данного числа. Когда надо найти все такие числа, его алгоритм оказывается намного экономнее, чем если просто проверять каждое число на простоту функцией IsSimple.

Вот, например, как получить все простые числа до 30:

1) Выписываются подряд все натуральные числа от 1 до данного.

2) 1 – не простое число. Вычеркиваем его.

3) Из следующих за ним чисел берем первое невычеркнутое. Оно простое. Оставляем его (подчеркиваем для наглядности синим) и...

4) вычеркиваем все кратные ему:

5) Было что-то вычеркнуто? Если да, то возвращаемся к последнему подчеркнутому числу и повторяем 3).
Если нет, то...

оставшиеся невычеркнутыми числа, подчеркнутые или нет, все суть простые.

  Задача 3. Доказать, что каждое составное число в результате исполнения этого алгоритма было вычеркнуто.

  Задача 4. а) Запрограммировать этот алгоритм. Найти все простые числа в пределах от 1 до 1000.
б) Вывести на экран таблицу найденных простых чисел в следующем виде:

 0:       2   3   5   7  11  13  17  19  23
10:  29  31  37  41  43  47  53  59  61  67
20:  71  73  79  83  89  97 101 103 107 109

(и т.д. По 10 чисел в строке. Перед знаком ':' стоит порядковый номер числа, следующего сразу после этого знака.)

Можно просмотреть готовое решение этой задачи.

Следующий раздел