Решение задачи 20.
Можно просто каждое число S, 1<S<=N, делить на все предыдущие натуральные числа k, 1<k<S, и если хоть один остаток от деления равен нулю, то S - не простое. Пусть S - составное, S=ab, при этом обязательно a<=, а b>=, так что для проверки простоты S имеет смысл проверять не все значения делителя k от 2 до S, а только k не превосходящее . Если число S - составное, то его можно разложить в произведение простых чисел, поэтому, так как мы уже нашли все простые числа меньшие S, то S имеет смысл делить только на простые числа, не превосходящие . Если S>2, то следует рассматривать только нечетные числа.
Алгоритм.
Пусть A - упорядоченное по возрастанию множество простых чисел, сначала A={2,3}.
Пусть N>3.
Для S от 5 до N с шагом 2 повторять
Для всякого простого числа x<= повторять
если остаток от деления S на x не равен нулю,
то S - простое, добавляем S в A
иначе S - составное.
|
