Prime sieve explanation

Questions / Help
1

I tried to modify an example from RosettaCode.org for a prime sieve algorithm. I’m not entirely sure I understood the original code. I tried to make sense of it with more explicit variable names but I was hoping someone could correct my understanding if I missed something. Also wondering why you have to prepopulate the odd primes with 3 and 5.

  def primes_to(limit) do
    # prepopulate with 2 so we only have to check odd numbers
    [2]
    |> Stream.concat(oddprimes())
    |> Enum.take_while(&(&1 < limit))
  end

  defp oddprimes() do
    # prepopulating with 3 and 5 is necessary but not sure why
    [3, 5]
    |> Stream.concat(
      Stream.iterate(
        {5, 25, 7, nil, %{9 => 6}},
        &check_next(&1)
      )
      |> Stream.map(fn {_, _, p, _, _} -> p end)
    )
  end

  # map ==> %{next_next_odd => increment}
  defp check_next({last_prime, last_prm_sq, next_odd, cached_primes?, map}) do
    cached_primes =
      if cached_primes? === nil do
        oddprimes() |> Stream.drop(1)
      else
        cached_primes?
      end

    next_next_odd = next_odd + 2

    # if the next number to check would be greater than the square of the last prime
    # advance the next known prime and its square as the new minimum step
    if next_next_odd >= last_prm_sq do
      inc = last_prime + last_prime
      next_cached_primes = cached_primes |> Stream.drop(1)
      [next_last_prime] = next_cached_primes |> Enum.take(1)

      check_next(
        {next_last_prime, next_last_prime * next_last_prime, next_next_odd, next_cached_primes,
         map |> Map.put(next_next_odd + inc, inc)}
      )
    else
      # if the next number to check is under the minimum step to advance
      # check if the map includes that number and remove it
      # find the first multiple of the increment for that number that is not
      # in the map and put it in the rmap (produced by removing the next number)
      #  with the increment as the value and check the next odd with the current
      #  last prime limits and cache
      if Map.has_key?(map, next_next_odd) do
        {inc, rmap} = Map.pop(map, next_next_odd)

        [next_candidate] =
          Stream.iterate(next_next_odd + inc, &(&1 + inc))
          |> Stream.drop_while(&Map.has_key?(rmap, &1))
          |> Enum.take(1)

        check_next(
          {last_prime, last_prm_sq, next_next_odd, cached_primes,
           Map.put(rmap, next_candidate, inc)}
        )
      else
        # if the next number to check is under the minimum step to advance
        # and it is not a key in the current map check the next odd
        # against the current last prime limits, cache, and map of increments
        {last_prime, last_prm_sq, next_next_odd, cached_primes, map}
      end
    end
  end
end
2

check_next uses oddprimes - which depends on check_next after the first two elements. The initial [3, 5] is similar to the “base case” in traditional recursive code; without it, the algorithm wouldn’t be able to get started.

1 Like
3

Here’s my contribution to this… Priority queues turn out to be your next step up from the basic wheel for immutable languages. Perhaps it’s useful?

1 Like
4

I guess I don’t understand the need to concat [3,5] but pass nil as the first round argument instead of just starting with [3,5] as the cached_primes? initial value.

5

Very nice work. Going to try a deeper dive into it to try and understand more fully. Thanks!

6

The initial value of cached_primes? is an infinite stream, the first two elements of which happen to be 3 and 5 - the rest of it is the result of iterating check_next.

3 Likes