stevensonmt

stevensonmt

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

Showing Posts 1 to 5

al2o3cr

al2o3cr

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.

the_wildgoose

the_wildgoose

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?

https://github.com/ewildgoose/elixir-primes

stevensonmt

stevensonmt OP

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.

stevensonmt

stevensonmt OP

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

al2o3cr

al2o3cr

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.

— All posts loaded —

Where Next? Top

Trending in Questions Top

katta
I having some trouble figuring out if I have set myself too strict of standards for my production server. Currently I can handle 75% of r...
New
brecabral
Documentation While reading the Scoped Routes section, I noticed that the documentation currently refers to a problem without explainin...
New
nseaSeb
Hello, I know there is an approach for handling lists that allows for optimized traversal, but I can’t recall the specific method (somet...
New
kpanic
Hi everyone, I am toying with the idea of building a “match maker” for giving personal help to people that wants to start coding. I sta...
New
velrest
So my question is quite simple and i have found no conclusive answer on forum, google or AI. Should we use :erlang.float for Integer to ...
New
asweet-confluent
I recently noticed that Elixir’s Logger defaults its primary log level to :debug when no :logger, :level application configuration is pre...
New
apz
I’m new to elixir and just tried to install the elixirLS extension for VScode(ium) and it is throwing some errors that I would like help ...
New

Other Trending Topics Top

GenericJam
Edit: 2026 May 15 - This post is archived. Mob is alive!! Main docs: mob v0.7.11 — Documentation A bit of explanation for the slightly c...
New
JesseHerrick
Hey, I’m Jesse and I’m the main contributor behind Dexter, a full-featured, lightning-fast Elixir LSP optimized for large codebases. It s...
New
mudasobwa
I am happy to introduce the very α version of the new programming language compiled to BEAM. Welcome Cure. It has literally three kille...
New
garrison
Hobbes is a low-level distributed database for the Elixir programming language. Hobbes provides a simple, safe, and scalable storage lay...
New
mhanberg
Hi everyone! The first release candidate for the Expert language server project is now available! We’ve published a press release detai...
New
budgie
A little off-topic, but I feel like people here have a good head on their shoulders. I used to be quite good at making software. Was luc...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews