有效地找到一个号码的所有除数 [英] Efficiently finding all divisors of a number
问题描述
所以我只是想找到一个给定的数字（除本数）的所有约数。
目前，我有这样的：
So I simply want to find all the divisors of a given number (excepting the number itself). Currently, I have this:
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为好。
where primes is a list of primes (assume it is correct, and is large enough). The algorithm works in the sense that it finds all the prime factors, but not all the factors (i.e. given 34534, it returns {1,2,17267,31,1114} but misses {62, 557} as 62 is a combination, and therefore misses 557 as well.
我也尝试刚开了许多的首要因素，但我不知道如何将其转换成所有正确的组合的名单。
I have also tried just getting the prime factors of a number, but I don't know how to convert that into a list of all of the correct combinations.
的code代表该算法如下：
The code for that algorithm is as follows:
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;
}
如何解决第一个，或者如何创建第二个组合的列表任何想法（我想preFER如此，因为它会更快）？
Any ideas on how to fix the first one, or how to create the list of combinations from the second one (I would prefer that as it would be faster)?
推荐答案
既然你已经拥有的主要因素清单，你想要做的是计算该列表的幂。
Since you already have a list of the prime factors, what you want to do is to compute the powerset of that list.
现在的一个问题是，你可能有在列表中重复（如20 = 2 * 2 * 5的主要因素），并集合不允许重复。因此，我们可以通过将其突出到表单{X，Y}，其中x是素数，y的结构使独特的列表的每个元素是在列表中首要的索引
Now one problem is that you might have duplicates in the list (e.g. the prime factors of 20 = 2 * 2 * 5) and sets don't allow duplicates. So we can make each element of the list unique by projecting it to a structure of the form {x, y} where x is the prime and y is the index of the prime in the list.
var all_primes = primes.Select((x, y) => new { x, y }).ToList();
现在 all_primes 的形式是{X，Y}其中x是素数，y的列表，在列表中的索引。
Now all_primes is a list of the form {x, y} where x is the prime and y is the index in the list.
然后我们计算幂集（定义 GetPowerSet 以下）：
Then we compute the power set (definition of GetPowerSet below):
var power_set_primes = GetPowerSet(all_primes);
所以 power_set_primes 是的IEnumerable＆LT; IEnumerable的＆LT; T＆GT;＆GT; ，其中 T 是匿名类型 {X，Y} 其中x和y的类型的 INT 。
So power_set_primes is an IEnumerable<IEnumerable<T>> where T is the anonymous type {x, y} where x and y are of type int.
所以，接下来我们计算每个元素的设置电源产品
So next we compute the product of the each element in the power set
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);
}
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];
}
这篇关于有效地找到一个号码的所有除数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
