Getting number factors

Question

I am trying to modify this algorithm to make it faster. What will 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; } 

Answer 1

The first optimization you could do is check only the square root of the number. This is due to the fact that factors fall into pairs, where one is smaller than the square root and the other is larger.

The only exception: if n is an exact square, then its square root is a factor of n , but is not part of a pair.

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

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

Thus, you do not need to check numbers above 5, because all other factors can already be deduced if you find the corresponding small coefficient in a pair.

Here is one way to do this 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 that you can use faster, but you may find that it is already fast enough for your needs, especially if you only need to work with 32-bit integers.

Answer 2

Reducing how high you have to go, since you could consciously stop at the square root of the number, although this is a precaution when choosing squares that will have an odd number of factors, but it helps to reduce how often the cycle should be executed.

Answer 3

• You can limit the upper limit of the FOR loop to numberToCheck / 2

• Start the cycle counter in 2 (if your number is even) or 3 (for odd values). This should allow you to check all other numbers, dropping the number of cycles by 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 4

There seems to be a lengthy discussion about this exact topic: An algorithm to calculate the number of divisors of a given number

Hope this helps

Answer 5

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

The following follows from the first: when you find a factor, divide it so that the resulting number is less. When you combine this with the fact that you only need to check the square root of the current number, this is a huge improvement. For example, consider N = 10714293844487412. It would be naive to take N steps. Checking to the square root takes sqrt (N) or about 100 million steps. But since factors 2, 2, 3, and 953 were discovered at an early stage, you really only need to check one million - a 100-fold improvement!

Another improvement: you do not need to check each number to find out if it divides your number, just prime numbers. If it is more convenient, you can use 2 and odd numbers, or 2, 3, and the numbers 6n-1 and 6n + 1 (base wheel).

Here is another nice improvement. If you can quickly determine if a number is prime, you can reduce the need for separation even further. Suppose that after removing small factors, you have 120528291333090808192969. Even checking to the square root will take a lot of time - 300 billion steps. But the Miller-Rabin test (very fast - perhaps 10 to 20 nanoseconds) will show that this number is composite. How does this help? This means that if you check your cube root and find no factors, then there will be exactly two prime numbers. If the number is a square, its coefficients are primary; if the number is not a square, the numbers are different strokes. This means that you can multiply your "total" by 3 or 4, respectively, to get the final answer - without even knowing the factors! This may be more important than you expected: the number of necessary steps is reduced from 300 to 50 million, 6000 times more!

The only problem with the above is that Miller-Rabin can only prove that numbers are compound; if he set the prime, he cannot prove that the number is prime. In this case, you might want to write a strength test function to save yourself the trouble of multiplying by the square root of a number. (Alternatively, you could just do a few more Miller-Rabin tests if you were satisfied with high confidence that your answer is correct, and not proof that it is. If the number passes 15 tests, then it is made up with probability less than 1 in a billion.)

Answer 6

Well, if you are going to use this function a lot, you can use the modified Eratosthenes algorithm http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes and save the andrers for the interval 1 to Max in the array. It will run IntializeArray () once and after it returns the responses to 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 the best solution is to check the unitll square root.

---

Note. I adjusted my code!

Answer 7

An easy-to-implement algorithm that will bring you much further than the trial division of Pollard Roh

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

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