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

问题描述

所有均分为x的数字.

我输入4会返回:4、2、1

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

edit:我知道这听起来很家庭作业.我正在编写一个小应用程序，以使用半随机测试数据填充某些产品表.其中两个属性是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 ++: 在所有人的帮助下，这就是我所追求的.再次感谢！

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添加到因子列表中.

realocode:

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

正如Jon Skeet所述，您也可以将其实现为IEnumerable<int>-使用

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屋！