 # Prime sieve explanation

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

|> 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
``````

`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

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

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.

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

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