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

Ещё один пример ленивых вычислений и рекурсии, менее тривиальный. Есть такое решето Эратосфена — простой, но эффективный алгоритм нахождения простых чисел. Выписываем дцать первых целых чисел, начиная с двойки; дальше мы их будем вычёркивать. Двойку, как невычеркнутую, объявляем простым числом, и вычёркиваем все числа, кратные её (4, 6, 8 и так далее). Берём следующее ещё невычеркнутое число (это будет три), объявляем его простым и вычёркиваем кратные ему. И так повторяем до конца (достаточно дойти до корня из дцати — все оставшиеся невычеркнутые заведомо будут простыми).

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

Итак, множество простых чисел — это множество всех чисел, начиная с двойки, за вычетом множества составных чисел.
Множество составных чисел — это множество чисел, кратных простым числам.

И это не какая-нибудь тавтология, это — рекурсия. Достаточно явно назвать двойку простым числом, чтобы это определение завертелось, вычисляя всё новые и новые простые числа.

Дальше ( не для слабонервных )