Getting Factors of a Number

问题:

Problem: I'm trying to refactor this algorithm to make it faster. What would be the first refactoring here for speed?

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

回答1:

The first optimization you could make is that you only need to check up to the square root of the number. This is because factors come in pairs where one is less than the square root and the other is greater.

One exception to this is if n is an exact square then its square root is a factor of n but not part of a pair.

For example if your number is 30 the factors are in these pairs:

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

So you don't need to check any numbers higher than 5 because all the other factors can already be deduced to exist once you find the corresponding small factor in the pair.

Here is one way to do it in 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;
}

There are other approaches you could use that are faster but you might find that this is already fast enough for your needs, especially if you only need it to work with 32-bit integers.

回答2:

Reducing the bound of how high you have to go as you could knowingly stop at the square root of the number, though this does carry the caution of picking out squares that would have the odd number of factors, but it does help reduce how often the loop has to be executed.

回答3:

Looks like there is a lengthy discussion about this exact topic here: Algorithm to calculate the number of divisors of a given number

Hope this helps

回答4:

The first thing to notice is that it suffices to find all of the prime factors. Once you have these it's easy to find the number of total divisors: for each prime, add 1 to the number of times it appears and multiply these together. So for 12 = 2 * 2 * 3 you have (2 + 1) * (1 + 1) = 3 * 2 = 6 factors.

The next thing follows from the first: when you find a factor, divide it out so that the resulting number is smaller. When you combine this with the fact that you need only check to the square root of the current number this is a huge improvement. For example, consider N = 10714293844487412. Naively it would take N steps. Checking up to its square root takes sqrt(N) or about 100 million steps. But since the factors 2, 2, 3, and 953 are discovered early on you actually only need to check to one million -- a 100x improvement!

Another improvement: you don't need to check every number to see if it divides your number, just the primes. If it's more convenient you can use 2 and the odd numbers, or 2, 3, and the numbers 6n-1 and 6n+1 (a basic wheel sieve).

Here's another nice improvement. If you can quickly determine whether a number is prime, you can reduce the need for division even further. Suppose, after removing small factors, you have 120528291333090808192969. Even checking up to its square root will take a long time -- 300 billion steps. But a Miller-Rabin test (very fast -- maybe 10 to 20 nanoseconds) will show that this number is composite. How does this help? It means that if you check up to its cube root and find no factors, then there are exactly two primes left. If the number is a square, its factors are prime; if the number is not a square, the numbers are distinct primes. This means you can multiply your 'running total' by 3 or 4, respectively, to get the final answer -- even without knowing the factors! This can make more of a difference than you'd guess: the number of steps needed drops from 300 billion to just 50 million, a 6000-fold improvement!

The only trouble with the above is that Miller-Rabin can only prove that numbers are composite; if it's given a prime it can't prove that the number is prime. In that case you may wish to write a primality-proving function to spare yourself the effort of factoring to the square root of the number. (Alternately, you could just do a few more Miller-Rabin tests, if you would be satisfied with high confidence that your answer is correct rather than a proof that it is. If a number passes 15 tests then it's composite with probability less than 1 in a billion.)

回答5:

1. You can limit the upper limit of your FOR loop to numberToCheck / 2

2. Start your loop counter at 2 (if your number is even) or 3 (for odd values). This should allow you to check every other number dropping your loop count by another 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;
   }
   

回答6:

Well if you are going to use this function a lot you can use modified algorithm of Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes and store answars for a interval 1 to Max in array. It will run IntializeArray() once and after it will return answers in 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];
}

But if you are not going to use this function a lot I think best solution is to check unitll square root.

---

Note: I have corrected my code!

回答7:

An easy to implement algorithm that will bring you much farther than trial division is Pollard Rho

Here is a Java implementation, that should be easy to adapt to C#: http://www.cs.princeton.edu/introcs/78crypto/PollardRho.java.html

回答8:

https://codility.com/demo/results/demoAAW2WH-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;
    }