高效查找數字的所有因數

Question

所以我只想查找給定數字的所有除數（除了數字本身）。 目前，我有這樣的：

public static List<int> proper_divisors(int x) 
{ 
    List<int> toreturn = new List<int>(); 
    toreturn.Add(1); 
    int i = 0; 
    int j=1; 
    int z = 0; 
    while (primes.ElementAt(i) < Math.Sqrt(x)) 
    { 
     if (x % primes.ElementAt(i) == 0) 
     { 
      toreturn.Add(primes.ElementAt(i)); 
      toreturn.Add(x/primes.ElementAt(i)); 
      j = 2; 
      z = (int)Math.Pow(primes.ElementAt(i), 2); 
      while (z < x) 
      { 
       if (x % z == 0) 
       { 
        toreturn.Add(z); 
        toreturn.Add(x/z); 
        j++; 
        z = (int)Math.Pow(primes.ElementAt(i), j); 
       } 
       else 
       { 
        z = x; 
       } 
      } 
     } 
     i++; 
    } 
    toreturn = toreturn.Distinct().ToList<int>(); 
    return toreturn; 
} 

其中素數是素數的列表，（假設它是正確的，足夠大）。 該算法的工作原理是它可以找到所有的素數因子，但不是所有的因子（即給出34534，它返回{1,2,17267,31,1114}但錯過{62，557}，因爲62是一個組合，因此錯過557爲好。

我也嘗試剛開了許多的首要因素，但我不知道如何將其轉換成所有的正確組合的列表。

的該算法的代碼如下：

public static List<int> prime_factors(int x) 
{ 
    List<int> toreturn = new List<int>(); 
    int i = 0; 
    while (primes.ElementAt(i) <= x) 
    { 
     if (x % primes.ElementAt(i) == 0) 
     { 
      toreturn.Add(primes.ElementAt(i)); 
      x = x/primes.ElementAt(i); 
     } 
     else 
     { 
      i++; 
     } 
    } 
    return toreturn; 
} 

關於如何解決的第一個，或如何創建組合從塞康列表中的任何想法d一個（我寧願那樣會更快）？

Answer 1

既然你已經擁有的主要因素清單，你想要做的是計算該列表的冪。

現在，一個問題是，你可能會在列表中重複（例如20 = 2 * 2 * 5的主要因素），但集合不允許重複。因此，我們可以通過將其投影到形式爲{x，y}的結構來使列表中的每個元素唯一，其中x是素數，y是列表中素數的索引。現在

var all_primes = primes.Select((x, y) => new { x, y }).ToList(); 

，all_primes的形式是{X，Y}，其中x是素數，y是該列表中的索引的列表。

然後我們計算功率設定（以下GetPowerSet定義）：

var power_set_primes = GetPowerSet(all_primes); 

因此，power_set_primes是IEnumerable<IEnumerable<T>>其中T是匿名類型{x, y}其中x和y是int類型。

接下來，我們計算的權力每個元素的產品集

foreach (var p in power_set_primes) 
{ 
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y); 
    factors.Add(factor); 
} 

全部放在一起：

var all_primes = primes.Select((x, y) => new { x, y }).ToList(); //assuming that primes contains duplicates. 
var power_set_primes = GetPowerSet(all_primes); 
var factors = new HashSet<int>(); 

foreach (var p in power_set_primes) 
{ 
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y); 
    factors.Add(factor); 
} 

從http://rosettacode.org/wiki/Power_Set爲冪的實現。

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list) 
{ 
    return from m in Enumerable.Range(0, 1 << list.Count) 
      select 
       from i in Enumerable.Range(0, list.Count) 
       where (m & (1 << i)) != 0 
       select list[i]; 
} 

Answer 2

有類似的問題before，它有一個使用IEnumerable的有趣解決方案。如果你想要所有的因數而不是因素，並且假設你至少使用C＃3。0您可以使用這樣的事情：

static IEnumerable<int> GetDivisors(int n) 
{ 
    return from a in Enumerable.Range(2, n/2) 
      where n % a == 0 
      select a;      
} 

，然後用它是這樣的：

foreach(var divisor in GetDivisors(10)) 
    Console.WriteLine(divisor); 

，或者，如果你想有一個列表，只需：

List<int> divisors = GetDivisors(10).ToList();