找到给定数字的所有因子的最佳方法

Question

所有数字均匀分配为x.

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

编辑:我知道这听起来像家庭作业.我正在编写一个小应用程序,用半随机测试数据填充一些产品表.其中两个属性是ItemMaximum和Item Multiplier.我需要确保乘数不会产生不合逻辑的情况,即购买1个项目会使订单超过允许的最大值.因此,这些因子将为我的测试数据提供有效值列表.

编辑++:这是我在所有人的帮助下使用的内容.再次感谢!

编辑#:我写了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;
        }
    }
}

在刻度线中.将数字分解为20次,每次5次:

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

将数字分解为20000时,每次5次:

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

Answer 1

伪代码:

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

正如Jon Skeet所提到的,您可以将其实现为IEnumerable<int>使用良率而不是添加到列表中.优点List<int>是,如果需要,它可以在返回之前进行排序.然后,你可以得到一个带有混合方法的排序枚举器,产生第一个因子并在循环的每次迭代中存储第二个因子,然后产生以相反顺序存储的每个值.

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

Answer 2

该%(余)运算符是用在这里的人.如果x % y == 0那时可x被整除y.(假设0 < y <= x)

我个人将此实现为返回IEnumerable<int>使用迭代器块的方法.

Answer 3

很晚但接受的答案(一段时间后)没有给出正确的结果.

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

Answer 4

作为扩展方法：

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

这是用法示例：

        foreach (int i in 4.Factors())
        {
            Console.WriteLine(i);
        }

请注意，我已针对清晰度进行了优化，而不是针对性能进行了优化。对于较大的值，i此算法可能需要很长时间。