找到给定数字的所有因数的最佳方法 [英] Best way to find all factors of a given number

问题描述

能整除 x 的所有数字.

All numbers that divide evenly into x.

我输入 4 它返回:4, 2, 1

I put in 4 it returns: 4, 2, 1

我知道这听起来像功课.我正在编写一个小应用程序，用半随机测试数据填充一些产品表.其中两个属性是 ItemMaximum 和 Item Multiplier.我需要确保乘数不会造成不合逻辑的情况，即再购买 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.

编辑++:这就是我在所有人的帮助下所做的.再次感谢！

edit++: This is what I went with after all the help from everyone. Thanks again!

edit#:我写了 3 个不同的版本，看看我更喜欢哪个版本，并针对小数和非常大的数进行因式分解测试.我会粘贴结果.

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.

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;
        }
    }
}

以滴答为单位.将数字分解为 20 时，每个数 5 次:

In ticks. When factoring the number 20, 5 times each:

• GetFactors1-5,445,881
• GetFactors2-4,308,234
• GetFactors3-2,913,659

当对数 20000 进行因式分解时，每个数 5 次:

When factoring the number 20000, 5 times each:

• GetFactors1-5,644,457
• GetFactors2-12,117,938
• GetFactors3-3,108,182

推荐答案

伪代码:

• 从 1 到数字的平方根循环，调用索引i".
• 如果 number mod i 为 0，则将 i 和 number/i 添加到因子列表中.

重新编码:

public List<int> Factor(int number) 
{
    var 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;
}

正如 Jon Skeet 提到的，您也可以将其实现为 IEnumerable - 使用 yield 而不是添加到列表中.List 的优点是它可以在需要时在返回之前进行排序.再说一次，您可以使用混合方法获得一个排序的枚举数，生成第一个因子并在循环的每次迭代中存储第二个因子，然后生成以相反顺序存储的每个值.

As Jon Skeet mentioned, you could implement this as an IEnumerable<int> as well - use yield instead 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.

您还需要做一些事情来处理传递给函数的负数的情况.

You will also want to do something to handle the case where a negative number passed into the function.

这篇关于找到给定数字的所有因数的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！