Глава 14. Поиск простых чисел

Постановка задачи
Идеи реализации
Наивный перебор
Оптимизированный перебор делителей
Перебор с запоминанием найденных простых чисел
Решето Эратосфена
Колёсный метод
Замечания
Разработка
Наивный перебор
Оптимизированный перебор делителей
Перебор с запоминанием найденных простых чисел
Решето Эратосфена
Колёсный метод
Готовая программа
Наивный (сплошной) перебор делителей
Оптимизированный перебор делителей
Перебор делителей среди запомненных простых
Решето Эратосфена
Колёсный метод
Сравнение разных версий программы

Простыми числами называются натуральные числа, которые делятся нацело лишь на себя и на единицу. Остальные натуральные числа называются составными. Единственное исключение — единицу — не относят ни к простым, ни к составным.

Нашей задачей будет последовательный поиск простых чисел, не превосходящих некоторого заданного числа.

Каждая из четырёх версий программы primes.pl, получив целое неотрицательное число в командной строке, выводит все простые числа, не превосходящие этого заданного, по одному в строке:

Информатика-54© А. Н. Швец