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
Hey guys,
I’ve got a huge CSV ( around 10 GB ) that needs to be processed hourly
Do you guys have any suggestions what is the best prac...
New
Hello!
Could someone please give me a help/sample code, how to delete a file from s3 using waffle/waffle_ecto from Phoenix app.
I creat...
New
I’m seeing that a list inside a Kino.DataTable will be interpreted as a charlist, even if the Kino.configure() is set to charlists: :as_l...
New
Anyone here using Honeybadger?
My Honeybadger account is being overwhelmed with noise from some bots. Seeing a lot of
Bandit.HTTPError...
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
Hi, I’ve just set up an application with ash_authentication. There is only magic link strategy for now, so there is no confirmation add o...
New
If a change or preparation module uses Ash.Changeset.get_argument/2 or Ash.Query.get_argument/2 (or any of the other get_argument functio...
New
Other Trending Topics
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
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
ExRatatui lets you cook up rich terminal UIs in Elixir, powered by Rust’s ratatui via Rustler NIFs. Build interactive terminal applicatio...
New
Hello everyone. After busy few months I am happy to announce v0.1.0 of Emerge & Solve.
They are GUI (Emerge) and State management (S...
New
Corex is an accessible, unstyled UI component library for Phoenix that integrates Zag.js state machines using Vanilla JavaScript and Live...
New
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #blog-post
- #elixir-ls
- #elixirconf-us
- #ai
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #hex
- #security
- #metaprogramming










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.