Source code in the erlang programming language

-module( sieve_of_eratosthenes ).

-export( [primes_upto/1] ).

primes_upto( N ) ->
	Ns = lists:seq( 2, N ),
	Dict = dict:from_list( [{X, potential_prime} || X <- Ns] ),
	{Upto_sqrt_ns, _T} = lists:split( erlang:round(math:sqrt(N)), Ns ),
	{N, Prime_dict} = lists:foldl( fun find_prime/2, {N, Dict}, Upto_sqrt_ns ),
	lists:sort( dict:fetch_keys(Prime_dict) ).



find_prime( N, {Max, Dict} ) -> find_prime( dict:find(N, Dict), N, {Max, Dict} ).

find_prime( error, _N, Acc ) -> Acc;
find_prime( {ok, _Value}, N, {Max, Dict} ) when Max > N*N ->
    {Max, lists:foldl( fun dict:erase/2, Dict, lists:seq(N*N, Max, N))};
find_prime( {ok, _Value}, _, R) -> R.

-module( sieve ).                                                                                                    
-export( [main/1,primes/2] ).                                                                                        
                                                                                                                     
main(N) -> io:format("Primes: ~w~n", [ primes(2,N) ]).                                                               
                                                                                                                     
primes(M,N) -> primes(M, N,lists:seq( M, N ),[]).                                                                    
                                                                                                                     
primes(M,N,_Acc,Tuples) when M > N/2-> out(Tuples);                                                                  

primes(M,N,Acc,Tuples) when length(Tuples) < 1 -> 
        primes(M,N,Acc,[{X, X} || X <- Acc]);                              

primes(M,N,Acc,Tuples) ->                                                                                            
        {SqrtN, _T} = lists:split( erlang:round(math:sqrt(N)), Acc ),                                                
        F = Tuples,                                                                                                  
        Ms = lists:filtermap(fun(X) -> if X > 0 -> {true, X * M}; true -> false end end, SqrtN),                     
        P = lists:filtermap(fun(T) -> 
            case lists:keymember(T,1,F) of true -> 
            {true, lists:keyreplace(T,1,F,{T,0})}; 
             _-> false end end,  Ms),                                                                                              
        AA = mergeT(P,lists:last(P),1 ),                                                                             
        primes(M+1,N,Acc,AA).                                                                                        
                                                                                                                     
mergeT(L,M,Acc) when Acc == length(L) -> M;                                                                          
mergeT(L,M,Acc) ->                                                                                                   
        A = lists:nth(Acc,L),                                                                                        
        B = M,                                                                                                       
        Mer = lists:zipwith(fun(X, Y) -> if X < Y -> X; true -> Y end end, A, B),                                    
        mergeT(L,Mer,Acc+1).                                                                                         
                                                                                                                     
out(Tuples) ->                                                                                                       
        Primes = lists:filter( fun({_,Y}) -> Y > 0 end,  Tuples),                                                    
        [ X || {X,_} <- Primes ].

-module(ossieve).
-export([main/1]).

sieve(Candidates,SearchList,Primes,_Maximum) when length(SearchList) == 0 ->
    ordsets:union(Primes,Candidates);
sieve(Candidates,SearchList,Primes,Maximum)  ->
     H = lists:nth(1,string:substr(Candidates,1,1)),
     Reduced1 = ordsets:del_element(H, Candidates),
     {Reduced2, ReducedSearch} = remove_multiples_of(H, Reduced1, SearchList),
     NewPrimes = ordsets:add_element(H,Primes),
     sieve(Reduced2, ReducedSearch, NewPrimes, Maximum).

remove_multiples_of(Number,Candidates,SearchList) ->                                 
    NewSearchList = ordsets:filter( fun(X) -> X >= Number * Number end, SearchList), 
    RemoveList = ordsets:filter( fun(X) -> X rem Number == 0 end, NewSearchList),
    {ordsets:subtract(Candidates, RemoveList), ordsets:subtract(NewSearchList, RemoveList)}.

main(N) ->      
    io:fwrite("Creating Candidates...~n"),
    CandidateList = lists:seq(3,N,2),
    Candidates = ordsets:from_list(CandidateList),
    io:fwrite("Sieving...~n"),
    ResultSet = ordsets:add_element(2,sieve(Candidates,Candidates,ordsets:new(),N)),
    io:fwrite("Sieved... ~w~n",[ResultSet]).

-module(sieveof).
-export([main/1,primes/1, primes/2]).                 
                                                      
main(X) -> io:format("Primes: ~w~n", [ primes(X) ]).  
                                 
primes(X) -> sieve(range(2, X)).                                         
primes(X, Y) -> remove(primes(X), primes(Y)).                            
                                                                         
range(X, X) -> [X];                                                      
range(X, Y) -> [X | range(X + 1, Y)].                                    
                                                                         
sieve([X]) -> [X];                                                       
sieve([H | T]) -> [H | sieve(remove([H * X || X <-[H | T]], T))].        
                                                                         
remove(_, []) -> [];                                                     
remove([H | X], [H | Y]) -> remove(X, Y);                                
remove(X, [H | Y]) -> [H | remove(X, Y)].

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p10_4
% vim:syn=erlang

-mode(compile).

main([N0]) ->
    N = list_to_integer(N0),
    ets:new(comp, [public, named_table, {write_concurrency, true} ]),
    ets:new(prim, [public, named_table, {write_concurrency, true}]),
    composite_mc(N),
    primes_mc(N),
    io:format("Answer: ~p ~n", [lists:sort([X||{X,_}<-ets:tab2list(prim)])]).

primes_mc(N) ->
    case erlang:system_info(schedulers) of
        1 -> primes(N);
        C -> launch_primes(lists:seq(1,C), C, N, N div C)
    end.
launch_primes([1|T], C, N, R) -> P = self(), spawn(fun()-> primes(2,R), P ! {ok, prm} end), launch_primes(T, C, N, R);
launch_primes([H|[]], C, N, R)-> P = self(), spawn(fun()-> primes(R*(H-1)+1,N), P ! {ok, prm} end), wait_primes(C);
launch_primes([H|T], C, N, R) -> P = self(), spawn(fun()-> primes(R*(H-1)+1,R*H), P ! {ok, prm} end), launch_primes(T, C, N, R).

wait_primes(0) -> ok;
wait_primes(C) ->
    receive
        {ok, prm} -> wait_primes(C-1)
    after 1000    -> wait_primes(C)
    end.

primes(N) -> primes(2, N).
primes(I,N) when I =< N ->
    case ets:lookup(comp, I) of
        [] -> ets:insert(prim, {I,1})
        ;_ -> ok
    end,
    primes(I+1, N);
primes(I,N) when I > N -> ok.


composite_mc(N) -> composite_mc(N,2,round(math:sqrt(N)),erlang:system_info(schedulers)).
composite_mc(N,I,M,C) when I =< M, C > 0 ->
    C1 = case ets:lookup(comp, I) of
        [] -> comp_i_mc(I*I, I, N), C-1
        ;_ -> C
    end,
    composite_mc(N,I+1,M,C1);
composite_mc(_,I,M,_) when I > M -> ok;
composite_mc(N,I,M,0) ->
    receive
        {ok, cim} -> composite_mc(N,I,M,1)
    after 1000    -> composite_mc(N,I,M,0)
    end.

comp_i_mc(J, I, N) -> 
    Parent = self(),
    spawn(fun() ->
        comp_i(J, I, N),
        Parent ! {ok, cim}
    end).

comp_i(J, I, N) when J =< N -> ets:insert(comp, {J, 1}), comp_i(J+I, I, N);
comp_i(J, _, N) when J > N -> ok.