primes.ex

# provides a stream of primes below n
# where range is a list from 2 to n
Stream.unfold(range,fn [head|tail] -> {head, tail |> Enum.filter(fn x -> rem(x,head) != 0 end)}; [] -> nil end)

# Parallelized version ~20% speed increase
    def eliminate_factors(workers, prime_number) do
      Enum.map(workers, fn worker ->
        send(worker, {:factor, prime_number})
      end)
      Enum.map(workers, fn worker ->
        receive do
          {:done, ^worker} -> nil
        end
      end)
    end

    def prime_worker(range, parent) do
      receive do
        {:factor, factor} ->
          maybe_primes = range |> Enum.filter(fn x -> rem(x, factor) != 0 end)
          send(parent, {:done, self})
          prime_worker(maybe_primes, parent)
        {:next} ->
          if range |> Enum.empty?() do
            send(parent, {:empty, self})
          else
            send(parent, {range |> List.first(), self});
          end
          prime_worker(range, parent)
        end
      end


      def prime_master(parent, [first_worker|rest], primes) do
        send(first_worker, {:next})
        receive do
          # first worker is out of primes move on to the next
          {:empty, ^first_worker} ->
            case rest do
              [] -> send(parent, {self, primes})
              _ -> prime_master(parent, rest, primes)
            end
          # first worker has a prime, remove everything from the
          # lists that it's a factor of
          {prime_factor, ^first_worker} ->
            eliminate_factors([first_worker] ++ rest, prime_factor)
            prime_master(parent, [first_worker] ++ rest, primes ++ [prime_factor])
        end
      end

      def prime_master(parent) do
        receive do
          {workers, primes} -> prime_master(parent, workers, primes)
        end
      end
      
      def find_primes_in_range(range, length) do
        {master,_} = Process.spawn(__MODULE__, :prime_master, [self], [:monitor]);
        bucket_size = :math.sqrt(length) |> Float.ceil |> Kernel.trunc
        workers = range |> Enum.to_list() |> Enum.chunk(div(length,bucket_size))
        |> Enum.reduce([], fn
          (chunk, []) ->
            {id, _} = Process.spawn(__MODULE__, :prime_worker,[chunk, master], [:monitor]);
            [id]
          (chunk, acc) ->
            {id, _} = Process.spawn(__MODULE__, :prime_worker,[chunk, master], [:monitor]);
            acc ++ [id];
          end)
        send(master, {workers, []})
        receive do
          {^master, primes} -> primes
        end
      end