高效查找数字的所有因数

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();