У меня есть код, который использует метод решета Эратосфена для генерации простых чисел до заданного предела N.
Метод:
- Разделить список нечетных чисел на сегменты
- Каждый сегмент передается процессу
- Сегменты просеиваются одновременно с набором Lp
Вот код:
%---------------------------------------------------------------------------------
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.
Если я вызову функцию primes_parr(100,2), код будет работать нормально. Даю мне вывод:
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
Но если я вызову primes_parr(100,3), вывод станет недействительным. С выходом:
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
Я хотел бы знать, что вызывает ошибку, если я разделил список на более чем два сегмента.