Skip to content

Nth Prime

Find the nth prime number.

Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.

// FILE: nth_prime.nomi
//# The nth prime number, found by trial division.

/// The `n`th prime, counting 2 as the first, or `None` when `n` is less than
/// one, since there is no zeroth prime.
pub fn prime(n: Int) -> Maybe<Int>
    if n < 1 then return None

    Iter.from(2)
    |> Iter.filter(is_prime)
    |> Iter.get(n - 1)
end

/// Whether `number` has no divisor between 2 and its square root.
fn is_prime(number: Int) -> Bool
    Iter.from(2)
    |> Iter.take_while(fn d -> d * d <= number)
    |> Iter.all_match(fn d -> number % d != 0)
end

// FILE: nth_prime_test.nomi
import nth_prime

test "prime"
    [
        ("first prime",              1,     Some(2)),
        ("second prime",             2,     Some(3)),
        ("sixth prime",              6,     Some(13)),
        ("big prime",                10001, Some(104743)),
        ("there is no zeroth prime", 0,     None),
    ]
    |> subtests (description, n, expected), description
        assert nth_prime.prime(n) == expected
    end
end
  • prime returns Maybe<Int>: there is no zeroth prime, and None says so without an error type for the one way to fail.
  • The primes are a lazy pipe, Iter.from(2) |> Iter.filter(is_prime) |> Iter.get(n - 1), rather than a sieve: the sieve needs a limit chosen in advance, and the 10,001st prime takes well under a second by trial division.
  • is_prime tries divisors up to the square root with Iter.take_while and Iter.all_match, which stops at the first divisor. The candidates come from Iter.from(2), so each is 2 or more, and % takes it as a divisor.
  • The five canonical cases are one subtests table.