Prime Target - Generating Prime Numbers in Elixir

Have you ever thought about how essential prime numbers are in our digital world? They’re the backbone of encryption, securing everything from passwords to GPG keys. If someone ever cracked the pattern behind prime numbers, modern security would collapse!

While I was watching a series called Prime Target, which highlights the unpredictability of primes, I had a thought: How would I generate prime numbers efficiently in Elixir? So let’s dive into the fascinating world of prime generation!

Generating Prime Numbers in Elixir

Elixir gives us multiple ways to generate prime numbers. From a basic approach to more efficient algorithms, we’ll explore different techniques:

• Naïve Primality Check – Simple but slow.
• Sieve of Eratosthenes – Fast for generating many primes.
• Streams & Concurrency – Optimized for performance.

Let’s break it down!

1. The Naïve Primality Test

The simplest way to check if a number is prime is by dividing it by numbers up to its square root.

defmodule PrimeChecker do
  def is_prime?(n) when n < 2, do: false
  def is_prime?(2), do: true
  def is_prime?(n) do
    2..:math.sqrt(n) |> Enum.all?(fn i -> rem(n, i) != 0 end)
  end
end

IO.inspect PrimeChecker.is_prime?(11) # true

✅ Pros: Easy to implement. ❌ Cons: Slow for large numbers.

2. The Sieve of Eratosthenes

This method efficiently finds all prime numbers up to a limit by eliminating multiples of each prime found.

defmodule PrimeGenerator do
  def sieve(limit) when limit < 2, do: []
  def sieve(limit) do
    2..limit |> Enum.to_list() |> remove_multiples()
  end

  defp remove_multiples([]), do: []
  defp remove_multiples([head | tail]) do
    [head | remove_multiples(Enum.filter(tail, &rem(&1, head) != 0))]
  end
end

IO.inspect PrimeGenerator.sieve(50)

✅ Pros: Much faster than the naïve method. ❌ Cons: Uses more memory.

3. Generating Infinite Primes with Streams

Elixir’s Stream module lets us lazily compute primes, generating as many as needed without holding them all in memory.

defmodule PrimeStream do
  def stream_primes do
    Stream.iterate(2, &next_prime/1)
  end

  defp next_prime(n) do
    next = n + 1
    if PrimeChecker.is_prime?(next), do: next, else: next_prime(next)
  end
end

IO.inspect PrimeStream.stream_primes() |> Enum.take(10)

✅ Pros: Saves memory, generates infinite primes. ❌ Cons: Still sequential, needs optimization.

4. Parallel Prime Computation with Task.async_stream

We can speed things up using parallel tasks to check primes concurrently.

defmodule ParallelPrimes do
  def generate(n) do
    Task.async_stream(2..100_000, &PrimeChecker.is_prime?/1, max_concurrency: 4)
    |> Stream.filter(fn {:ok, true} -> true; _ -> false end)
    |> Enum.take(n)
  end
end

IO.inspect ParallelPrimes.generate(10)

✅ Pros: Uses multiple CPU cores. ❌ Cons: Inefficient for small n.

5. Ultimate Optimization: ETS + Flow

By combining ETS (Erlang Term Storage) for caching and Flow for parallel execution, we get a high-performance solution.

defmodule PrimeFlowETS do
  require Flow
  @table :prime_cache

  def start_link do
    :ets.new(@table, [:set, :public, :named_table])
    :ets.insert(@table, {2, true})
    {:ok, self()}
  end

  def get_primes(n) do
    primes = :ets.tab2list(@table) |> Enum.map(fn {p, _} -> p end)
    if length(primes) >= n, do: Enum.take(primes, n), else: find_more_primes(n)
  end

  defp find_more_primes(n) do
    2..100_000
    |> Flow.from_enumerable()
    |> Flow.partition(stages: System.schedulers_online())
    |> Flow.filter(&is_prime?/1)
    |> Flow.each(fn prime -> :ets.insert(@table, {prime, true}) end)
    |> Enum.take(n)
  end

  defp is_prime?(n) do
    primes = :ets.tab2list(@table) |> Enum.map(fn {p, _} -> p end)
    Enum.all?(primes, fn p -> rem(n, p) != 0 end)
  end
end

PrimeFlowETS.start_link()
IO.inspect PrimeFlowETS.get_primes(20)

✅ Pros: Super-fast, multi-core, avoids recomputation. ❌ Cons: More complex setup.

Conclusion

Method	Pros	Cons
Naïve Check	Simple to implement	Slow for large numbers
Sieve of Eratosthenes	Fast for many primes	Uses more memory
Streams	Generates infinite primes	Still sequential
Parallel Tasks	Uses multiple CPU cores	Less efficient for small n
ETS + Flow	Ultra-fast, avoids recalculations	More complex setup

What’s the Best Approach?

• If you need a quick solution, use the Sieve of Eratosthenes.
• For infinite primes, go with Streams.
• For maximum performance, combine ETS + Flow.

🚀 What’s next? Try modifying the GenServer to store primes or explore distributed computing for even faster prime generation!

Do you have a preferred approach for prime number generation? Let’s discuss in the comments!