C# 找到给定数字的所有因数的最佳方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/239865/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Best way to find all factors of a given number
提问by Echostorm
All numbers that divide evenly into x.
所有能整除 x 的数字。
I put in 4 it returns: 4, 2, 1
我输入 4 它返回：4, 2, 1
edit: I know it sounds homeworky. I'm writing a little app to populate some product tables with semi random test data. Two of the properties are ItemMaximum and Item Multiplier. I need to make sure that the multiplier does not create an illogical situation where buying 1 more item would put the order over the maximum allowed. Thus the factors will give a list of valid values for my test data.
编辑：我知道这听起来像功课。我正在编写一个小应用程序，用半随机测试数据填充一些产品表。其中两个属性是 ItemMaximum 和 Item Multiplier。我需要确保乘数不会造成不合逻辑的情况，即再购买 1 件商品会使订单超过允许的最大值。因此，这些因素将为我的测试数据提供有效值列表。
edit++: This is what I went with after all the help from everyone. Thanks again!
编辑++：这就是我在所有人的帮助下所做的。再次感谢！
edit#: I wrote 3 different versions to see which I liked better and tested them against factoring small numbers and very large numbers. I'll paste the results.
编辑#：我写了 3 个不同的版本，看看我更喜欢哪个版本，并针对小数字和非常大的数字对它们进行了测试。我会粘贴结果。
static IEnumerable<int> GetFactors2(int n)
{
return from a in Enumerable.Range(1, n)
where n % a == 0
select a;
}
private IEnumerable<int> GetFactors3(int x)
{
for (int factor = 1; factor * factor <= x; factor++)
{
if (x % factor == 0)
{
yield return factor;
if (factor * factor != x)
yield return x / factor;
}
}
}
private IEnumerable<int> GetFactors1(int x)
{
int max = (int)Math.Ceiling(Math.Sqrt(x));
for (int factor = 1; factor < max; factor++)
{
if(x % factor == 0)
{
yield return factor;
if(factor != max)
yield return x / factor;
}
}
}
In ticks. When factoring the number 20, 5 times each:
在蜱。对数字 20 进行因式分解，每个数 5 次：
- GetFactors1-5,445,881
- GetFactors2-4,308,234
- GetFactors3-2,913,659
- GetFactors1-5,445,881
- GetFactors2-4,308,234
- GetFactors3-2,913,659
When factoring the number 20000, 5 times each:
对数字 20000 进行因式分解时，各 5 次：
- GetFactors1-5,644,457
- GetFactors2-12,117,938
- GetFactors3-3,108,182
- GetFactors1-5,644,457
- GetFactors2-12,117,938
- GetFactors3-3,108,182
采纳答案by Chris Marasti-Georg
pseudocode:
伪代码：
- Loop from 1 to the square root of the number, call the index "i".
- if number mod i is 0, add i and number / i to the list of factors.
- 从 1 到数字的平方根循环，调用索引“i”。
- 如果 number mod i 为 0，则将 i 和 number / i 添加到因子列表中。
realocode:
重新编码：
public List<int> Factor(int number) {
List<int> factors = new List<int>();
int max = (int)Math.Sqrt(number); //round down
for(int factor = 1; factor <= max; ++factor) { //test from 1 to the square root, or the int below it, inclusive.
if(number % factor == 0) {
factors.Add(factor);
if(factor != number/factor) { // Don't add the square root twice! Thanks Jon
factors.Add(number/factor);
}
}
}
return factors;
}
As Jon Skeet mentioned, you could implement this as an IEnumerable<int>as well - use yieldinstead of adding to a list. The advantage with List<int>is that it could be sorted before return if required. Then again, you could get a sorted enumerator with a hybrid approach, yielding the first factor and storing the second one in each iteration of the loop, then yielding each value that was stored in reverse order.
正如 Jon Skeet 所提到的，您也可以将其实现IEnumerable<int>为 - 使用yield而不是添加到列表中。with 的优点List<int>是它可以在需要时在返回之前进行排序。再说一次，您可以使用混合方法获得一个排序的枚举数，生成第一个因子并在循环的每次迭代中存储第二个因子，然后生成以相反顺序存储的每个值。
You will also want to do something to handle the case where a negative number passed into the function.
您还需要做一些事情来处理传递给函数的负数的情况。
回答by Jon Skeet
The %(remainder) operator is the one to use here. If x % y == 0then xis divisible by y. (Assuming 0 < y <= x)
该%（余）运算符是一个用在这里。如果x % y == 0thenx被 整除y。（假设0 < y <= x）
I'd personally implement this as a method returning an IEnumerable<int>using an iterator block.
我个人将其实现为IEnumerable<int>使用迭代器块返回 的方法。
回答by Marcel Popescu
Linq solution:
林克解决方案：
IEnumerable<int> GetFactors(int n)
{
Debug.Assert(n >= 1);
return from i in Enumerable.Range(1, n)
where n % i == 0
select i;
}
回答by Jay Bazuzi
As extension methods:
作为扩展方法：
public static bool Divides(this int potentialFactor, int i)
{
return i % potentialFactor == 0;
}
public static IEnumerable<int> Factors(this int i)
{
return from potentialFactor in Enumerable.Range(1, i)
where potentialFactor.Divides(i)
select potentialFactor;
}
Here's an example of usage:
下面是一个使用示例：
foreach (int i in 4.Factors())
{
Console.WriteLine(i);
}
Note that I have optimized for clarity, not for performance. For large values of ithis algorithm can take a long time.
请注意，我已针对清晰度而不是性能进行了优化。对于i这个算法的大值可能需要很长时间。
回答by Jay Bazuzi
Here it is again, only counting to the square root, as others mentioned. I suppose that people are attracted to that idea if you're hoping to improve performance. I'd rather write elegant code first, and optimize for performance later, after testing my software.
正如其他人提到的，这里又是一次，只计算平方根。我想如果您希望提高性能，人们会被这个想法所吸引。我宁愿先编写优雅的代码，然后在测试我的软件后优化性能。
Still, for reference, here it is:
不过，作为参考，这里是：
public static bool Divides(this int potentialFactor, int i)
{
return i % potentialFactor == 0;
}
public static IEnumerable<int> Factors(this int i)
{
foreach (int result in from potentialFactor in Enumerable.Range(1, (int)Math.Sqrt(i))
where potentialFactor.Divides(i)
select potentialFactor)
{
yield return result;
if (i / result != result)
{
yield return i / result;
}
}
}
Not only is the result considerably less readable, but the factors come out of order this way, too.
不仅结果的可读性大大降低，而且这些因素也以这种方式失序。
回答by mspmsp
Wouldn't it also make sense to start at 2 and head towards an upper limit value that's continuously being recalculated based on the number you've just checked? See N/i (where N is the Number you're trying to find the factor of and i is the current number to check...) Ideally, instead of mod, you would use a divide function that returns N/i as well as any remainder it might have. That way you're performing one divide operation to recreate your upper bound as well as the remainder you'll check for even division.
从 2 开始并朝着根据您刚刚检查的数字不断重新计算的上限值前进不是也有意义吗？请参阅 N/i（其中 N 是您要查找的因子的数字，而 i 是要检查的当前数字...）理想情况下，您可以使用除法函数而不是 mod，该函数也返回 N/i就像它可能有的任何剩余部分一样。这样你就可以执行一个除法运算来重新创建你的上限以及你将检查均匀除法的余数。
Math.DivRem http://msdn.microsoft.com/en-us/library/wwc1t3y1.aspx
Math.DivRem http://msdn.microsoft.com/en-us/library/wwc1t3y1.aspx
回答by Pablo Retyk
Another LINQ style and tying to keep the O(sqrt(n)) complexity
另一种 LINQ 风格并保持 O(sqrt(n)) 复杂度
static IEnumerable<int> GetFactors(int n)
{
Debug.Assert(n >= 1);
var pairList = from i in Enumerable.Range(1, (int)(Math.Round(Math.Sqrt(n) + 1)))
where n % i == 0
select new { A = i, B = n / i };
foreach(var pair in pairList)
{
yield return pair.A;
yield return pair.B;
}
}
回答by call me Steve
Very late but the accepted answer (a while back) didn't not give the correct results.
很晚了，但接受的答案（不久前）没有给出正确的结果。
Thanks to Merlyn, I got now got the reason for the square as a 'max' below the corrected sample. althought the answer from Echostorm seems more complete.
多亏了 Merlyn，我现在得到了平方作为校正样本下方的“最大值”的原因。虽然 Echostorm 的答案似乎更完整。
public static IEnumerable<uint> getFactors(uint x)
{
for (uint i = 1; i*i <= x; i++)
{
if (0 == (x % i))
{
yield return i;
if (i != (x / i))
{
yield return x / i;
}
}
}
}
回答by JEJoll
If you use doubles, the following works: use a for loop iterating from 1 up to the number you want to factor. In each iteration, divide the number to be factored by i. If (number / i) % 1 == 0, then i is a factor, as is the quotient of number / i. Put one or both of these in a list, and you have all of the factors.
如果您使用双精度数，则以下操作有效：使用 for 循环从 1 迭代到您要分解的数字。在每次迭代中，将要分解的数字除以 i。如果 (number / i) % 1 == 0，那么 i 是一个因子，就像 number / i 的商。将其中一个或两个放在一个列表中，您就拥有了所有因素。
回答by Spencer
I did it the lazy way. I don't know much, but I've been told that simplicity can sometimes imply elegance. This is one possible way to do it:
我用懒惰的方式做到了。我知道的不多，但有人告诉我，简单有时也意味着优雅。这是一种可能的方法：
public static IEnumerable<int> GetDivisors(int number)
{
var searched = Enumerable.Range(1, number)
.Where((x) => number % x == 0)
.Select(x => number / x);
foreach (var s in searched)
yield return s;
}
EDIT: As Kraang Prime pointed out, this function cannot exceed the limit of an integer and is (admittedly) not the most efficient way to handle this problem.
编辑：正如 Kraang Prime 所指出的，这个函数不能超过整数的限制，并且（不可否认）不是处理这个问题的最有效方法。
