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
endok prime (5 cases)
test result: ok. 5 passed, 0 failed
How it’s written
Section titled “How it’s written”primereturnsMaybe<Int>: there is no zeroth prime, andNonesays 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_primetries divisors up to the square root withIter.take_whileandIter.all_match, which stops at the first divisor. The candidates come fromIter.from(2), so each is 2 or more, and%takes it as a divisor.- The five canonical cases are one
subteststable.