Как минимум ваш код должен быть
primes = [2,3,5,7,11,13]
genPrimes primes max = go primes (length primes) 1 (last primes + 2)
where
go prs len d t
| len >= max = prs
| (prs !! d) > (floor . sqrt . fromIntegral) t
= go (prs++[t]) (len+1) 1 (t + 2)
| t `rem` (prs !! d) == 0 = go prs len 1 (t + 2)
| t `rem` (prs !! d) /= 0 = go prs len (d + 1) t
test n = print $ genPrimes primes n
main = test 20
Затем вы реорганизуете его таким образом (абстрагируя тесты, выполненные для каждого номера кандидата, как функцию noDivs):
genPrimes primes max = go primes (length primes) (last primes + 2)
where
go prs len t
| len >= max = prs
| noDivs (floor . sqrt . fromIntegral $ t) t prs
= go (prs++[t]) (len+1) (t + 2)
| otherwise = go prs len (t + 2)
noDivs lim t (p:rs)
| p > lim = True
| t `rem` p == 0 = False
| otherwise = noDivs lim t rs
тогда вы переписываете noDivs как
noDivs lim t = foldr (\p r -> p > lim || rem t p /= 0 && r) False
затем вы замечаете, что go просто фильтрует числа так, что проходит тест noDivs:
genPrimes primes max = take max (primes ++ filter theTest [t, t+2..])
where
t = last primes + 2
theTest t = noDivs (floor . sqrt . fromIntegral $ t) t
но это пока не работает, потому что theTest нужно передать primes (целые новые простые числа по мере их обнаружения) в noDivs, но мы строим это whole_primes список (как take max (primes ++ ...)), есть ли замкнутый круг? Нет, потому что мы проверяем только до квадратного корня числа:
genPrimes primes max = take max wholePrimes
where
wholePrimes = primes ++ filter theTest [t, t+2..]
t = last primes + 2
theTest t = noDivs (floor . sqrt . fromIntegral $ t) t wholePrimes
Это работает сейчас. Но, наконец, в genPrimes сейчас нет ничего особенного, это просто прославленный вызов take, и первоначальный список primes может быть сокращен, так что мы получаем (немного изменив расположение аргументов для noDivs, чтобы сделать его интерфейс более общий):
primes = 2 : 3 : filter (noDivs $ tail primes) [5, 7..]
noDivs factors t = -- return True if the supplied list of factors is too short
let lim = (floor . sqrt . fromIntegral $ t)
in foldr (\p r-> p > lim || rem t p /= 0 && r) True factors
-- all ((/=0).rem t) $ takeWhile (<= lim) factors
-- all ((/=0).rem t) $ takeWhile ((<= t).(^2)) factors
-- and [rem t f /= 0 | f <- takeWhile ((<= t).(^2)) factors]
Глобальный список primes теперь неопределенно определен (т.е. «бесконечен»). Следующий шаг заключается в том, чтобы понять, что между последовательными квадратами простых чисел длина списка факторов для проверки будет одинаковой, увеличиваясь на 1 для каждого нового сегмента. Тогда , что, имея все факторы заранее в качестве префикса (известной длины) глобального списка primes, мы можем напрямую генерировать их кратные значения (таким образом, каждый генерируется только из его простые факторы), вместо того, чтобы проверять каждое число, является ли оно кратным любому из простых факторов ниже его квадратного корня, в последовательности.