Number of Factors of a Large Integer

You should follow me on Twitter. While you're at it, take a moment to subscribe to GMAT Hacks via RSS or Email.


Occasionally a GMAT question will ask you for the number of factors of a certain integer. Usually that integer will be large (441 is the object of one question that comes to mind), since the question wouldn't be very challenging otherwise.

For a long time, I did exercises like that the old-fashioned way: starting with 1, finding all the numbers along the way that were divisible by 441. It can be helpful to use a prime factorization, but even with that assistance, the job requires some brute force.

No longer.

The method I'm about to show you isn't for the math-averse; it introduces permutations into a question type that doesn't need them, so unless you're comfortable with the idea of factors and you aren't confused by permutations, this should help you.

Find the Number of Factors

The concept behind this method is that the prime factorization of a number determines all of its factors. If a number is divisible by 2, for instance, 2 will be a factor of many of the number's factors. In fact, each factor of a number is built up of one or more of the number's other factors.

Take 18, for instance. The prime factors of 18 are 2 and 3; the prime factorization is 2 times 3 times 3, or (2^1)(3^2).

Consider each of 18's factors in terms of its own prime factorization:

  • 1 = (2^0)(3^0)
  • 2 = (2^1)(3^0)
  • 3 = (2^0)(3^1)
  • 6 = (2^1)(3^1)
  • 9 = (2^0)(3^2)
  • 18 = (2^1)(3^2)

If you look at all of those numbers in terms of their factorizations, you'll see every possible arrangement of 2 to the 0 or 1 power with 3 to the 0, 1, or 2 power. That's no accident.

To generalize that method, here's your approach:

  1. Find the prime factorization of a number (each one of the number's prime factors raised to the appropriate power).
  2. List all of the exponents.
  3. Add one to each of the exponents. (Remember, it's possible to raise the prime factor to the zero power.)
  4. Multiply the resulting numbers.

Find the Number of Factors of 196

Let's try those steps with 196. I've never seen a specific GMAT question asking for the number of factors of 196, but it's exactly the sort of number they are likely to use.

  1. The prime factorization: 196 = (2^2)(7^2)
  2. The powers: 2 and 2
  3. Add one to the powers: 3 and 3
  4. Multiply the results: (3)(3) = 9

There are 9 factors of 196. To see what those are, work through the permutations of the exponents 0, 1, and 2 for the prime factors 2 and 7:

  • (2^0)(7^0) = 1
  • (2^1)(7^0) = 2
  • (2^2)(7^0) = 4
  • (2^0)(7^1) = 7
  • (2^1)(7^1) = 14
  • (2^2)(7^1) = 28
  • (2^0)(7^2) = 49
  • (2^1)(7^2) = 98
  • (2^2)(7^2) = 196

I can't imagine a GMAT question on which you'll need to figure out what all the factors are, but it's nice to see that the method works. This is the sort of technique that should be very far down your list: It's just not that high of a priority. But for those of you attempting to add 20 or 30 points to an already high score, it's a handy time-saving method.



About the author: Jeff Sackmann has written many GMAT preparation books, including the popular Total GMAT Math, Total GMAT Verbal, and GMAT 111. He has also created explanations for problems in The Official Guide, as well as 1,800 practice GMAT math questions.

Total GMAT Math

The comprehensive guide to the GMAT Quant section. It's "far and away the best study material available," including over 300 realistic practice questions and more than 500 exercises!
Click to read more.