獲取數字的所有因子（迭代器攤牌:)

Question

給出數字的所有素數因子以及它們的多重性（最高冪次）。
需求是產生該數字的所有因素。

我舉一個例子：

總理因素：

• 2（功率：3）
• 3（功率：1）

（意味着數爲2^3 * 3^1 = 24 ）

預期的結果是：
1，2，3，4，6，8，12，24

我想這樣做（在C＃中）與一些鏈式自定義迭代器，每個素數因子，將從0計數到該素數的權力。

你將如何實現這一點？使用您的首選語言。

這是從Project Euler

Answer 1

考慮所有可能的權力組合。對於每個組合，將素數提高到相應的功率，然後乘以結果。

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

Answer 2

我先拍與problem #23無手頭的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，就會添加一個解決方案。

Answer 3

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] 

排序結果，

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 ，p ，＆hellip;，p^Ë每個對（p,e）進行因式分解，取其乘積每個列表都在笛卡爾積中設置。

Answer 4

如果你不關心單個除數，但對n個全部約數的總和，你可能想看看Divisor Function：

因此除數的

總和

是

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 

Read more