Алгоритм для нахождения всех простых чисел меньших n

Как-то я был свидетелем следующего диалога. Некто, назовём его учеником решил научится программированию. Учитель т.е. более опытный его товарищ решил ему в этом помочь. Надо сказать, что кое-какие знания у ученика уже были, поэтому учитель недолго думаю решил дать ему практическое задание, которое он в своё время получил одним из первых.

Задание следующие: дано некоторое натуральное число n (скажем n=20). Нужно написать программу, которая выдаст на экран все простые числа больше 1 и меньше n (т.е. 2,3,5,7,11,13,17,19).

Очевидно, что имелось в виду решение или с помощью перебора делителей для каждого числа, либо с помощью решета Эратосфена, так как это задача по программированию, а не математике...

Так вот, у ученика, не получалось решить эту задачу, учитель пытался дать подсказку. И вот учитель и говорить: "сперва нужно найти закрытую формулу для генерации простых чисел".

Я чуть не упал со стула. Вслух, я просто рассмеялся. "Я имел в виду закрытую математическую формулу для определения простоты числа"-поправил себя учитель.

Ситуация улучшилась. Здесь, хотя бы решение, в принципе известно. Хотя закрытой алгебраической формулы лично я не знаю, но существует неалгебраические такие формулы, впрочем универсальный, детерминированный, полиномиальный, безусловный такой алгоритм появился только в 2002 году.

Я, конечно, понимаю, что учитель просто коряво высказал свою мысль. Он имел в виду, "подумай, как проверить, является ли данное число составным", но получилось то, что получилось. :-)

Ниже есть продолжение.

Вернёмся, однако, к первому высказанному утверждению. Ученик ведь не знает ни теста Агравала — Каяла — Саксены (ссылка на него приведена выше, он впервые был опубликованный 6 августа 2002 года. До этой публикации принадлежность задачи распознавания простоты классу P являлась открытой проблемой), ни теста Миллера, который является детерминированным, но этот тест основан на недоказанной расширенной гипотезе Римана. Я думаю о расширенной гипотезе Римана не знает и учитель. Также я не думаю, что имелся в виду теста Рабина-Миллера (вероятностный полиномиальный тест простоты), которые не опирается на расширенную гипотезе Риману.

Попробую объяснить более простыми словами. Фраза

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

просит не много не мало найти закономерность, описывающей распределение простых чисел среди натуральных. Всего навсего, решить нерешённую до сих пор математическую проблему. :-)

Замечу, в то время как не найдено какой-либо закономерности, описывающей распределение простых чисел среди натуральных, Риман обнаружил, что количество простых чисел, не превосходящих x, — функция распределения простых чисел, обозначаемая $\pi(x)$ — выражается через распределение так называемых "нетривиальных нулей" дзета-функции. Вот об этом и говорит расширенная гипотеза Римана. Гипотеза Римана (обычная) входит в список семи "проблем тысячелетия", за решение каждой из которых Математический институт Клэя (Clay Mathematics Institute, Кембридж, Массачусетс) выплатит награду в один миллион долларов США. Можно сказать, что ученику предлагалось "для разминки" решить эту проблему. :-)