获得数字的因素

Question

问题:我正在尝试重构此算法以使其更快.什么是速度的第一次重构？

public int GetHowManyFactors(int numberToCheck)
    {
        // we know 1 is a factor and the numberToCheck
        int factorCount = 2; 
        // start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor
        for (int i = 2; i < numberToCheck; i++) 
        {
            if (numberToCheck % i == 0)
                factorCount++;
        }
        return factorCount;
    }

Answer 1

您可以进行的第一个优化是您只需要检查数字的平方根.这是因为因子成对出现,其中一个小于平方根而另一个小于平方根.

一个例外是if n是一个精确的平方,那么它的平方根是一个因子n而不是一对的一部分.

例如,如果您的数字为30,那么这些因素就是:

• 1 x 30
• 2 x 15
• 3 x 10
• 5 x 6

因此,您不需要检查任何高于5的数字,因为一旦您在对中找到相应的小因子,就可以推断出所有其他因素都已存在.

这是在C#中执行此操作的一种方法:

public int GetFactorCount(int numberToCheck)
{
    int factorCount = 0;
    int sqrt = (int)Math.Ceiling(Math.Sqrt(numberToCheck));

    // Start from 1 as we want our method to also work when numberToCheck is 0 or 1.
    for (int i = 1; i < sqrt; i++)
    {
        if (numberToCheck % i == 0)
        {
            factorCount += 2; //  We found a pair of factors.
        }
    }

    // Check if our number is an exact square.
    if (sqrt * sqrt == numberToCheck)
    {
        factorCount++;
    }

    return factorCount;
}

您可以使用的其他方法更快,但您可能会发现这已经足够快,可以满足您的需求,特别是如果您只需要使用32位整数.