获得数字的因素

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

您可以进行的第一个优化是您只需要检查到数字的平方根即可。这是因为一个因子成对的因素，其中一个小于平方根，另一个较大。

一个例外是 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位整数一起使用。

Answer 2

减少您必须有意停止在数字的平方根上必须走的高度的界限，尽管这确实谨慎挑选出具有奇数因素的正方形，但它确实有助于减少频率循环必须执行。

Answer 3

看来这里对这个确切主题进行了漫长的讨论： 计算给定数字的分隔线的算法

希望这可以帮助

Answer 4

首先要注意的是，找到所有主要因素就足够了。一旦有了这些，就很容易找到总共分的数量：对于每个序列，将1次添加到它出现的次数并将它们乘以。因此，对于12 = 2 * 2 * 3，您有（2 + 1） *（1 + 1）= 3 * 2 = 6因子。

接下来是从第一个开始的：当您找到一个因子时，将其分开，以使结果数较小。当您将其与仅需要检查到当前数字的平方根的事实相结合时，这将是一个巨大的进步。例如，考虑n = 10714293844487412。天真的步骤。检查到其平方根，需要SQRT（N）或约1亿步。但是，由于因素2、2、3和953很早就发现了您实际上只需要检查一百万次 - 改善了100倍！

另一个改进：您不需要检查每个数字即可查看它是否划分您的数字，只是素数。如果更方便，则可以使用2和奇数，或2、3，以及数字6n-1和6n+1（基本的轮筛）。

这是另一个不错的进步。如果您可以快速确定一个数字是否是素数，则可以进一步减少划分的需求。假设在删除小因素之后，您有120528291333090808192969。即使检查到其平方根也将花费很长时间 - 3000亿步。但是米勒 - 拉宾测试（非常快 - 也许是10至20 纳秒）将表明该数字是复合的。这有什么帮助？这意味着，如果您检查到其立方体根，找不到任何因素，那么剩下两个素数。如果数字是正方形，则其因素为主要因素；如果数字不是正方形，则数字是不同的素数。这意味着您可以分别将“运行总计”乘以3或4，以获取最终答案 - 即使不知道因素！这可以比您猜到的更大：所需步骤数量从3000亿降至5000万，改进了6000倍！

上述唯一的麻烦是，米勒 - 拉宾只能证明数字是复合的。如果给出了素数，则无法证明该数字是素数。在这种情况下，您可能希望编写一个原始功能，以使自己摆脱数字的平方根的努力。 （或者，如果您对答案是正确的，而不是证明它是的证明，则可以再进行几次Miller-Rabin测试。如果一个数字通过15个测试，那么它的概率小于1的复合材料十亿美元。）

Answer 5

1. 您可以将循环的上限限制为数字检查 / 2

2. 从2（如果您的数字为偶数）或3（对于奇数值）开始循环计数器。这应该使您可以检查其他每个数字，从而将循环数量降低50％。

   public int GetHowManyFactors(int numberToCheck)
   {
     // we know 1 is a factor and the numberToCheck
     int factorCount = 2; 
   
     int i = 2 + ( numberToCheck % 2 ); //start at 2 (or 3 if numberToCheck is odd)
   
     for( ; i < numberToCheck / 2; i+=2) 
     {
        if (numberToCheck % i == 0)
           factorCount++;
     }
     return factorCount;
   }
   

Answer 6

好吧，如果您要大量使用此功能，则可以使用Eratosthenes的修改算法 http://en.wikipedia.org/wiki/sieve_of_eratosthenes 并将Answars存储为间隔1到最大数组。它将一次和之后运行Intializearray（）将在0（1）中返回答案。

const int Max =1000000;
int arr [] = new int [Max+1];

public void InitializeArray()
{
    for(int i=1;i<=Max;++i)
        arr[i]=1;//1 is factor for everyone

    for(int i=2;i<=Max;++i)
        for(int j=i;i<=Max;i+=j)
           ++arr[j];
}
public int GetHowManyFactors(int numberToCheck)
{
   return arr[numberToCheck];
}

但是，如果您不经常使用此功能，我认为最好的解决方案是检查UniTll Square Root。

---

注意：我已经更正了我的代码！

Answer 7

一种易于实现的算法，将为您带来比审判部门更远的算法是 Pollard Rho

这是Java实现，应该很容易适应C＃： http://www.cs.princeton.edu/introcs/78crypto/pollardrho.java.html

Answer 8

https://codility.com/demo/results/demoaaw2wh2wh-mgf/

 public int solution(int n) {
      var counter = 0;          
      if (n == 1) return 1;
      counter = 2; //1 and itself      
      int sqrtPoint = (Int32)(Math.Truncate(Math.Sqrt(n)));
      for (int i = 2; i <= sqrtPoint; i++)
      {
        if (n % i == 0)
        {
          counter += 2; //  We found a pair of factors.         
        }       
      }
      // Check if our number is an exact square.
      if (sqrtPoint * sqrtPoint == n)
      {
        counter -=1;
      }

      return counter;
    }