Elixir implementation of the Sieve of Eratosthenes algorithm for finding prime numbers.

sieve_of_eratosthenes.ex

defmodule SieveOfEratosthenes do
  @doc """
  https://www.baeldung.com/cs/prime-number-algorithms

  Naive implementation of the Sieve Of Eratosthenes for finding primes below `number`
  """
  @spec primes(number) :: list
  def primes(1), do: []

  def primes(n) do
    numbers =
      cond do
        n <= 3 -> Enum.to_list(2..n)
        true -> Enum.to_list(2..trunc(:math.sqrt(n)))
      end

    sieve(numbers, [])
    |> Enum.reverse()
  end

  defp sieve([], primes), do: primes

  defp sieve([p | rest], primes) do
    primes = [p | primes]
    sieve(for(n <- rest, rem(n, p) != 0, do: n), primes)
  end
end