Prime Factors
Break a natural number into its prime factors, smallest first.
Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.
// FILE: prime_factors.nomi
//# The prime factors of a number.
/// The prime factors of `value`, smallest first, each repeated as often as it
/// divides `value`.
pub fn factors(value: Int) -> List<Int>
factors_from(value, 2)
end
fn factors_from(n: Int, divisor: PositiveInt) -> List<Int>
case
n == 1 -> []
divisor * divisor > n -> [n]
n % divisor == 0 -> [divisor, ..factors_from(n / divisor, divisor)]
_ -> factors_from(n, divisor + 1)
end
end
// FILE: prime_factors_test.nomi
import prime_factors
test "factors"
[
("no factors", 1, []),
("prime number", 2, [2]),
("another prime number", 3, [3]),
("square of a prime", 9, [3, 3]),
("product of first prime", 4, [2, 2]),
("cube of a prime", 8, [2, 2, 2]),
("product of second prime", 27, [3, 3, 3]),
("product of third prime", 625, [5, 5, 5, 5]),
("product of first and second prime", 6, [2, 3]),
("product of primes and non-primes", 12, [2, 2, 3]),
("product of primes", 901255, [5, 17, 23, 461]),
("factors include a large prime", 93819012551, [11, 9539, 894119]),
]
|> subtests (description, value, expected), description
assert prime_factors.factors(value) == expected
end
endok factors (12 cases)
test result: ok. 12 passed, 0 failed
How it’s written
Section titled “How it’s written”- Trial division by recursion:
factors_from(n, divisor)either conses a factor onto the rest ([divisor, ..factors_from(n / divisor, divisor)]) or moves to the next divisor in tail position. The non-tail call happens once per factor, so the depth is at most 63. - It stops as soon as
divisor * divisor > n, which keeps the large-prime case (93819012551) to about 9,500 steps. - A
casewith no subject picks among the four conditions in order. - One
subteststable for all 12 cases.