Skip to content

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
end
  • 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 case with no subject picks among the four conditions in order.
  • One subtests table for all 12 cases.