I have a code that uses the Sieve of Eratosthenes method to generate prime numbers up to a given limit N.
Method:
Here is the code:
%---------------------------------------------------------------------------------
primes(N) ->
simple_sieve(lists:seq(3,N,2),[],N).
simple_sieve(Lin,Lp,N) -> [H|_] = Lin,
case H*H < N of
true -> simple_sieve([X || X <- Lin, X rem H =/= 0], [H|Lp], N);
false -> lists:reverse(Lp) ++ Lin
end.
%---------------------------------------------------------------------------------
primes_parr(N, Num_blocks) ->
Pid_stem = self(),
SQ = round(math:sqrt(N)),
Lp = primes(SQ), io:fwrite("List of primes: ~w~n", [Lp]),
Block_size = round(N/Num_blocks),
ok = leaf_spawn(Pid_stem, Lp, SQ, Block_size, Num_blocks),
stem_loop(Lp, 0, Num_blocks).
stem_loop(Lp, Primes, 0) ->
1 + length(Lp) + Primes;
stem_loop(Lp, Primes, Num_blocks) ->
receive
{leaf_done, _, Leaf_nums} ->
stem_loop(Lp, Primes+Leaf_nums, Num_blocks-1)
end.
leaf_spawn(_, _, _, _, 0) -> ok;
leaf_spawn(Pid_stem, Lp, SQ, Block_size, Num_blocks) ->
case (Num_blocks==1) of
true -> case (SQ rem 2 == 0) of
true -> Start = SQ+1;
false -> Start = SQ
end;
false -> Start = 1
end,
First = (Num_blocks-1)*Block_size + Start,
Last = Num_blocks*Block_size,
io:fwrite("Start: ~w | Finish: ~w ~n", [First,Last]),
spawn(fun() -> leaf(Pid_stem, Num_blocks, First, Last, [], Lp) end),
leaf_spawn(Pid_stem, Lp, SQ, Block_size, Num_blocks-1).
leaf(Pid_stem, Leaf_id, First, Last, Leaf_nums, []) ->
L = ordsets:subtract(lists:seq(First,Last,2),lists:usort(Leaf_nums)),
io:fwrite("The sublist is: ~w~n", [L]),
Pid_stem ! {leaf_done, Leaf_id, length(ordsets:subtract(lists:seq(First,Last,2),lists:usort(Leaf_nums)))};
leaf(Pid_stem, Leaf_id, First, Last, Leaf_nums, [H|T]) ->
case (H*H =< Last) of
true ->
case H*H >= First of
true ->
leaf(Pid_stem, Leaf_id, First, Last, lists:seq(H*H, Last, 2*H) ++ Leaf_nums, T);
false ->
K = round((First - H*H)/(2*H)),
leaf(Pid_stem, Leaf_id, First, Last, lists:seq(H*H + 2*K*H, Last, 2*H) ++ Leaf_nums, T)
end;
false ->
leaf(Pid_stem, Leaf_id, First, Last, Leaf_nums, [])
end.
If I call the function primes_parr(100,2), the code works just fine. Giving me the output:
List of primes(Lp): [3,5,7]
Start: 51 | Finish: 100
Start: 11 | Finish: 50
The sublist is: [53,59,61,67,71,73,79,83,89,97]
The sublist is: [11,13,17,19,23,29,31,37,41,43,47]
25 %no. of primes
But if I call primes_parr(100,3), the output becomes invalid. With the output being:
List of primes(Lp): [3,5,7]
Start: 67 | Finish: 99
Start: 34 | Finish: 66
Start: 11 | Finish: 33
The sublist is: [67,71,73,79,83,89,97]
The sublist is: [34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66]
The sublist is: [11,13,17,19,23,29,31]
35 %no. of primes
I'd like to know what's causing the error if I split the list into more than two segments.
Judging by your invalid output
The sublist is: [67,71,73,79,83,89,97]
The sublist is: [34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66] %% HERE
The sublist is: [11,13,17,19,23,29,31]
somewhere your code assumes that a starting number of a range to sieve is odd.
Indeed,
leaf(Pid_stem, Leaf_id, First, Last, Leaf_nums, []) ->
L = ordsets:subtract(lists:seq(First,Last,2),lists:usort(Leaf_nums)),
io:fwrite("The sublist is: ~w~n", [L]),
Pid_stem ! {leaf_done, Leaf_id, length(L)}; %% reuse the L !!
assumes that First
is odd, when it calculates lists:seq(First,Last,2)
.
This should be simple to fix. Just add 1
to First
if it's even, immediately after you've calculated it inside leaf_spawn
. (edit: better do it here, on entry into leaf
, so its requirement is clearly seen and is enforced by it itself).
Also, sometimes your biggest prime in Lp
is also included as the first prime in the lowest block (e.g. for N=121
, N=545
).