Два быстрых однопроцессных генератора Erlang Prime; sprimes генерирует все простые числа до 2 м за ~ 2,7 с, а у ~ 3 с на моем компьютере (Macbook с 2,4 ГГц Core 2 Duo). Оба основаны на Сите Эратосфена, но поскольку Erlang лучше всего работает со списками, а не с массивами, оба хранят список не исключенных простых чисел, проверяя делимость текущей головой и сохраняя накопитель проверенных простых чисел. Оба также реализуют простое колесо для первоначального сокращения списка.
-module(primes).
-export([sprimes/1, wheel/3, fprimes/1, filter/2]).
sieve([H|T], M) when H=< M -> [H|sieve([X || X<- T, X rem H /= 0], M)];
sieve(L, _) -> L.
sprimes(N) -> [2,3,5,7|sieve(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), math:sqrt(N))].
wheel([X|Xs], _Js, M) when X > M ->
lists:reverse(Xs);
wheel([X|Xs], [J|Js], M) ->
wheel([X+J,X|Xs], lazy:next(Js), M);
wheel(S, Js, M) ->
wheel([S], lazy:lazy(Js), M).
fprimes(N) ->
fprimes(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), [7,5,3,2], N).
fprimes([H|T], A, Max) when H*H =< Max ->
fprimes(filter(H, T), [H|A], Max);
fprimes(L, A, _Max) -> lists:append(lists:reverse(A), L).
filter(N, L) ->
filter(N, N*N, L, []).
filter(N, N2, [X|Xs], A) when X < N2 ->
filter(N, N2, Xs, [X|A]);
filter(N, _N2, L, A) ->
filter(N, L, A).
filter(N, [X|Xs], A) when X rem N /= 0 ->
filter(N, Xs, [X|A]);
filter(N, [_X|Xs], A) ->
filter(N, Xs, A);
filter(_N, [], A) ->
lists:reverse(A).
lazy: lazy / 1 и lazy: next / 1 относятся к простой реализации псевдо-ленивых бесконечных списков:
lazy(L) ->
repeat(L).
repeat(L) -> L++[fun() -> L end].
next([F]) -> F()++[F];
next(L) -> L.
Генерация простых чисел с помощью сит не является хорошим местом для параллелизма (но он может использовать параллелизм при проверке делимости, хотя операция не достаточно сложна, чтобы оправдать дополнительные издержки всех параллельных фильтров, которые я написал до сих пор).
`