找到一个给定数量的在C＃中的所有因素的最佳方法 [英] Best way to find all factors of a given number in C#

问题描述

这整除x中的数字。

我把4它返回：4，2，1

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

编辑：我知道这听起​​来homeworky。我正在写一个小应用程序，以用半随机测试数据的一些产品表。两个属性是ItemMaximum和项目乘数。我需要确保乘数不会创建一个不合逻辑的情况下购买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!

编辑＃：我写了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-5445881
• GetFactors2-4308234
• GetFactors3-2913659

在保人数20000，每5次：

When factoring the number 20000, 5 times each:

• GetFactors1-5644457
• GetFactors2-12117938
• GetFactors3-3108182

推荐答案

伪code：

• 循环从1至数的平方根，称之为指数I。
• 如果数模i为0，添加我和编号/我要的因素清单。

realo code：

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

由于乔恩斯基特提到的，你可以实现这是一个的IEnumerable＆LT; INT＆GT; 以及 - 使用的收益而不是添加到列表。与的好处名单，其中，INT＆GT; 的是，它可以返回之前，如果需要排序。再说，你可以得到一个排序枚举用一种混合方法，得到第一因子和存储第二一个在循环的每次迭代，然后得到已存储在相反的顺序的每个值。

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.

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