#!/usr/bin/ghci

============================================================
(copyleft) 2010, ФМШ, с/к Haskell
============================================================

\textbf{Задача.} Написать код, генерирующий потенциально бесконечный
список простых чисел. Оптимизация по скорости, памяти и краткости
кода не требуется.

\textbf{Решение.} Разобъем решение на несколько шагов.

1. Введем свой предикат, показывающий, что a делится нацело на b, т.е.
a:b (или тоже самое b|a):

\begin{code}

de a b = if ((rem a b) == 0) then True else False

\end{code}

Здесь rem - это функция, возвращающая остаток от деления.
Если он равен нулю, то деление нацело есть, иначе - нет.
Будем применять данный предикат так: a `de` b.

2. Определим множество делителей числа n:

\begin{code}

divs_of n = [t | t <- [2..(n-1)], n `de` t] 

\end{code}

Список порожден значениями t из интервала от 2 до n-1, которые являются
делителями числа n.

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

\begin{code}

isprime x = if null (divs_of x) then True else False

\end{code}

4. Все готово. Зададим требуемое множество:

\begin{code}

primeset = [n | n <- [2..], isprime n]

\end{code}

Для проверки работоспособности кода его необходимо скопировать в файл 
с именем, скажем, prime.lhs, затем запустить интерпретатор ghci и в нем
загрузить этот файл командой :l prime.lhs.

После чего можно напечатать первые сто простых чисел командой take 100 primeset.
Для интересы попробуйте задать divs_of 360, или проверить isprime (10^100000+1).

\textbf{Задачи для самостоятельного размышления.} Написать оптимизированный код.
Например, использовать элементы решета Эратосфена для просмотра делителей.
Сделать код компактней. Или написать функцию, ищущию простое число больше 
данного натурального.