获取一个数的所有因子（迭代器对决 :)

Question

你已经拥有一个数字的所有质因数及其重复次数（最高幂）。要求是生成该数字的所有因子。

让我举个例子：

质因数：

2（幂：3）

3（幂：1）

（意味着该数字为2^3 * 3^1 = 24）

预期结果为：

1、2、3、4、6、8、12、24

我正在考虑使用一些链接的自定义迭代器（在C#中），每个质因数一个，它们将从0计数到该质数的幂。

你会如何实现这个？使用你喜欢的语言。

这与Project Euler的problem #23相关。

- Cristian Diaconescu

---

我不知道 Project Euler 管理员对于 SO 公开他们问题的解决方案有多喜欢。请参考 http://stackoverflow.com/questions/1010739/help-with-project-euler-200-closed。 - user50685

在这种情况下，我认为可以接受，因为问题要求标准算法，而不是解决问题的方案。此外，这个问题仍然相当简单，并且这不是最佳方法。 - starblue

+1，这根本不是欧拉计划问题。这个问题非常普遍，肯定是一个“真正”的编程问题。（指关闭它的两个投票者认为它“不是一个真正的问题”） - ShreevatsaR

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, 3, 4, 6, 8, 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

---

J.

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

---

这些都实现了同样的算法，即为每个因数对(p, e)，生成列表p^0,p^1,...,p^e，并取所有这些列表中的笛卡尔积的乘积。

- ephemient

---

我应该指出，这些语言中没有一个真正具有“迭代器”的概念...（好吧，在Perl中你可以制作绑定数组，但那很麻烦）。然而，由于Haskell的惰性求值，普通列表就像其他语言中的迭代器一样，但使用起来更加容易。 - ephemient

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解决方案。）

- Stephan202

Answer 3

如果您不关心单个除数，而是关心n的所有除数之和，您可能会想看看约数函数：

因此，n的除数之和为

是

- ymihere

---

这个回答更与实际的PE问题有关，而不是我的问题；不过这是一个很好的见解！+1 我也喜欢texify.com的提示-这是你的吗？ - Cristian Diaconescu

Answer 4

我最初是没有IDE的，所以可能会有一些错误。

struct PrimePower
{
    public PrimePower(Int32 prime, Int32 power) : this()
    {
        this.Prime = prime;
        this.Power = power;
    }

    public Int32 Prime { get; private set; }
    public Int32 Power { get; private set; }
}

然后就是这个递归函数。

public IEnumerable<Int32> GetFactors(IList<PrimePowers> primePowers, Int32 index)
{
    if (index < primePowers.Length() - 1)
    {
        Int32 factor = 1;
        for (Int32 p = 0; p <= primePowers[index].Power; p++)
        {
            yield return factor * GetFactors(primePowers, index + 1);
            factor *= primePowers[index].Prime;
        }
    }
    else if (index = primePowers.Length() - 1)
    {
        Int32 factor = 1;
        for (Int32 p = 0; p <= primePowers[index].Power; p++)
        {
            yield return factor * GetFactors(primePowers, index + 1);
            factor *= primePowers[index].Prime;
        }
    }
    else
    {
        throw new ArgumentOutOfRangeException("index");
    }
}

这也可以是一个扩展方法，IList<PrimerPower> 可能会被弱化为 IEnumerable<PrimePower>，只需使用几个 Skip() 和 Take() 调用即可。我也不喜欢在各个调用之间传递索引，但另一种选择是为每个调用复制质数幂列表。因此，我认为迭代解决方案更可取 - 如果我再次拥有 IDE，我将添加一个。

- Daniel Brückner

Answer 5

非常容易做到。事实上，我在我的博客上写了一篇关于这个问题的文章。请查看以下代码。

#Application lists all factors/divisors for a number.
targetNumber=input('What number do you want the factors for?\n> ')
factors=[]
for i in range(1,targetNumber):
    if targetNumber%i==0:
        factors.append(i)
    elif targetNumber/i==1:
        factors.append(targetNumber)
        break
print factors

阅读更多

- user1675111