获取一些数字的所有因素(迭代器摊牌:)

Question

您将获得一个数字的所有主要因子,以及它们的多重性(最高权力).
要求是产生该数字的所有因素.

让我举个例子:

主要原因:

• 2(电源:3)
• 3(电源:1)

(意思是数字是 2^3 * 3^1 = 24)

预期结果是:
1,2,3,4,6,8,12,24

我正在考虑使用一些链式自定义迭代器(在C#中),每个素数因子一个,从0到该素数的幂.

你会如何实现这个？使用您的首选语言.

这是有关问题#23从项目欧拉

Answer 1

哈斯克尔.

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]

要对结果进行排序,

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

Ĵ.

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

这些都实现了相同的算法,即为分解中的每对(p,e)生成列表p ⁰,p ¹,...,p ^e,并将笛卡尔积中每组的乘积乘以所有这些列表.

Answer 2

考虑所有可能的权力组合。对于每个组合，将素数乘以相应的幂，然后将结果相乘。

>>> from functools import reduce
>>> from itertools import product, starmap
>>> from operator import mul 
>>> 
>>> def factors(prime_factors):
...     primes, powers = zip(*prime_factors)
...     power_combos = product(*(range(p + 1) for p in powers))
...     prime_combos = (zip(primes, c) for c in power_combos)
...     return (reduce(mul, starmap(pow, c)) for c in prime_combos)
... 
>>> sorted(factors([(2, 3), (3, 1)]))
[1, 2, 3, 4, 6, 8, 12, 24]

该代码使用Python 3.0。除了对 的调用之外sorted，它还专门使用迭代器。

旁注：太糟糕了，这个问题似乎很不受欢迎。我希望看到一些功能解决方案被发布。（稍后我可能会尝试编写 Haskell 解决方案。）