Prime Target: Generating Prime Numbers in Elixir

Introduction

While watching the series Prime Target, which turns the unpredictability of prime numbers into a plot device, I got curious: what are the nice ways to generate primes in Elixir?

Here are four, from the obvious to the parallel, each with the small detail that makes it correct.

1. The naive primality test

The simplest check: a number is prime if nothing between 2 and its square root divides it.

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

PrimeChecker.is_prime?(11) # => true
PrimeChecker.is_prime?(15) # => false

Two details matter here. :math.sqrt/1 returns a float, and Elixir ranges need integers, so it has to be wrapped in trunc/1. And the explicit //1 step is what makes the range empty rather than descending when the square root is below 2 — without it, 2..1 would iterate [2, 1], and dividing by 1 would wrongly reject small primes like 3.

Simple, but slow for large numbers.

2. A recursive sieve

We can generate every prime up to a limit by repeatedly keeping a number and filtering out its multiples from the rest.

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

PrimeGenerator.sieve(30) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Much faster than checking each number in isolation, at the cost of holding the whole list in memory.

3. An infinite stream

Elixir’s Stream module lets us produce primes lazily, computing only as many as we ask for.

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

PrimeStream.stream_primes() |> Enum.take(10)
# => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Stream.iterate/2 emits its seed and then feeds each value to the next call, so this yields primes forever without ever building a full list. It’s still sequential, though.

4. Parallel checks with Task.async_stream

For a range of candidates, Task.async_stream/3 checks several at once across cores.

defmodule ParallelPrimes do
  def generate(n) do
    2..100_000
    |> Task.async_stream(fn x -> {x, PrimeChecker.is_prime?(x)} end, max_concurrency: 4)
    |> Stream.filter(fn {:ok, {_x, prime}} -> prime end)
    |> Stream.map(fn {:ok, {x, _}} -> x end)
    |> Enum.take(n)
  end
end

ParallelPrimes.generate(10)
# => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The trick is what each task returns. Task.async_stream wraps results as {:ok, value}, and value is whatever the function returned. If the function returns just the boolean, you get back a list of {:ok, true} tuples, not the primes. Returning the pair {x, is_prime?(x)} keeps the number attached, so after filtering you can map back to the actual primes.

Which one to use

Method	Good for	Trade-off
Naive check	Testing a single number	Slow at scale
Recursive sieve	All primes up to a limit	Holds the list in memory
Stream	An open-ended supply of primes	Sequential
Task.async_stream	Scanning a big range	Overhead hurts for small counts

For generating a batch, the sieve is the pragmatic default. For an unbounded source, the stream. And when the range is large and the check is the bottleneck, Task.async_stream puts your cores to work — as long as you remember to carry the number through the pipeline, not just the boolean.