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
Trending in Questions
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
Documentation
While reading the Scoped Routes section, I noticed that the documentation currently refers to a problem without explainin...
New
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
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
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
I recently noticed that Elixir’s Logger defaults its primary log level to :debug when no :logger, :level application configuration is pre...
New
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
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
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
I am happy to introduce the very α version of the new programming language compiled to BEAM.
Welcome Cure.
It has literally three kille...
New
Hobbes is a low-level distributed database for the Elixir programming language.
Hobbes provides a simple, safe, and scalable storage lay...
New
Hi everyone!
The first release candidate for the Expert language server project is now available!
We’ve published a press release detai...
New
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
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ai
- #ecto-query
- #elixirconf-us
- #blog-post
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #elixirconf-eu
- #api
- #forms
- #metaprogramming
- #hex











Showing Posts 1 to 5- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
al2o3cr
check_nextusesoddprimes- which depends oncheck_nextafter 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
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
I guess I don’t understand the need to concat
[3,5]but passnilas the first round argument instead of just starting with[3,5]as thecached_primes?initial value.stevensonmt
Very nice work. Going to try a deeper dive into it to try and understand more fully. Thanks!
al2o3cr
The initial value of
cached_primes?is an infinite stream, the first two elements of which happen to be3and5- the rest of it is the result of iteratingcheck_next.