有效地找到数字的所有除数

所以我只想找到给定数字的所有除数（除了数字本身）。 目前，我有这个：

public static List proper_divisors(int x) { List toreturn = new List(); 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(); return toreturn; } 

其中primes是素数列表（假设它是正确的，并且足够大）。 算法在找到所有素因子的意义上起作用，但不是所有因子（即给定34534，它返回{1,2,17267,31,1114}但是错过{62,557}，因为62是一个组合，因此也错过了557。

我也尝试过获取数字的素因子，但我不知道如何将其转换为所有正确组合的列表。

该算法的代码如下：

 public static List prime_factors(int x) { List toreturn = new List(); 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; } 

关于如何修复第一个，或如何从第二个创建组合列表的任何想法（我希望，因为它会更快）？

Answer 1

由于您已经有一个素数因子列表，您要做的是计算该列表的powerset。

现在，一个问题是你可能在列表中有重复项（例如20 = 2 * 2 * 5的素数因子），但是集合不允许重复。 因此，我们可以通过将列表的每个元素投影到{x，y}forms的结构来使列表中的每个元素唯一，其中x是素数，y是列表中素数的索引。

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

现在， all_primes是{x，y}forms的列表，其中x是素数，y是列表中的索引。

然后我们计算幂集（下面的GetPowerSet定义）：

 var power_set_primes = GetPowerSet(all_primes); 

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

接下来，我们计算功率集中每个元素的乘积

 foreach (var p in power_set_primes) { var factor = p.Select(x => xx).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(); foreach (var p in power_set_primes) { var factor = p.Select(x => xx).Aggregate(1, (x, y) => x * y); factors.Add(factor); } 

来自http://rosettacode.org/wiki/Power_Set，用于实现powerset。

 public IEnumerable> GetPowerSet(List 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

之前有一个类似的问题，它有一个使用IEnumerable的有趣解决方案。 如果你想要所有的除数而不是因子，假设你至少使用C＃3.0，你可以使用这样的东西：

 static IEnumerable 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，只需：

 List divisors = GetDivisors(10).ToList();