Get all factors of a number (iterators showdown :)

Question

You are given all the prime factors of a number, along with their multiplicities (highest powers).
The requirment is to produce all the factors of that number.

Let me give an example:

Prime factors:

• 2 (power: 3)
• 3 (power: 1)

(meaning the number is 2^3 * 3^1 = 24)

The expected result is:
1, 2, 3, 4, 6, 8, 12, 24

I'm thinking of doing this (in C#) with some chained custom iterators, one for each prime factor, that would count from 0 to the power of that prime number.

How would you implement this? Use your preferred language.

This is related to problem #23 from Project Euler

Answer 1

Haskell.

cartesianWith f xs = concatMap $ \y -> map (`f` y) xs
factorsOfPrimeFactorization =
    foldl (cartesianWith (*)) [1] . map (\(p, e) -> map (p^) [0..e])

> factorsOfPrimeFactorization [(2, 3), (3, 1)]
[1,2,4,8,3,6,12,24]

To sort the result,

import Data.List
cartesianWith f xs = concatMap $ \y -> map (`f` y) xs
factorsOfPrimeFactorization =
    sort . foldl (cartesianWith (*)) [1] . map (\(p, e) -> map (p^) [0..e])

---

Perl.

sub factors {
    my %factorization = @_;
    my @results = (1);
    while (my ($p, $e) = each %factorization) {
        @results = map {my $i = $_; map $i*$_, @results} map $p**$_, 0..$e;
    }
    sort {$a <=> $b} @results;
}

print join($,, factors(2, 3, 3, 1)), $/;  # => 1 2 3 4 6 8 12 24

---

J.

   /:~~.,*/"1/{:@({.^i.@{:@>:)"1 ] 2 3 ,: 3 1
1 2 3 4 6 8 12 24

---

These all implement the same algorithm, which is to generate the list p⁰,p¹,…,p^e for each pair (p,e) in the factorization, and take the product of each set in the Cartesian product across all those lists.