If you’re thigh-deep in your GMAT prep (or still remember some of your math from high school), chances are you’re already familiar with the “factor rainbow” method of listing any number’s given factors. For example, if we were to list all the factors of 60, we would match 1 with 60, then 2 with 30, then 3 with 20, etc.
If you need to know exact factors for a problem, this is the way to go. But if you’re only interested in finding HOW MANY factors the number has, it can get a bit tedious.
Lucky for you, there’s an easier way. Once again, prime numbers come to the rescue! (Are you starting to under stand my evangelical passion for prime numbers?)
Believe it or not, there’s a way you can find the number of factors of ANY given num ber without even looking at any of the factors themselves.
Here’s how you do it.
Let’s say the num ber we’re inter ested in is 2,940. First step: Find the number’s prime factorization:
2940
10 * 294
(2*5) * (2*147)
(2*5) * (2*7*21)
(2*5) * (2*7*7*3)
Prime fac tor iza tion: 2^2 * 3^1 * 5^1 * 7^2
For those of you who just want to know the strategy and don’t care about how or why it works, I’ll cut to the chase:
Our prime factorization was 2^2 * 3^1 * 5^1 * 7^2. In order to find the number of factors, all we need to do is add 1 to each exponent and multiply the results:
(2+1)*(1+1)*(1+1)*(2+1) = 3*2*2*3 = 36.
2,940 has a total of 36 factors. That’s it!
Now, for any curious and intrepid mathletes out there, let’s get into the nitty-gritty of exactly why this method works:
If we take the prod uct of ANY combination of these prime fac tors, we will get a fac tor of the orig i nal value (2,940). For exam ple, we could take both 2s, one 3, and one 7, and we can mul ti ply them together to get 2*2*3*7 = 84, which is a factor of 2,940.
As a result, we can treat this like a combinations problem. We have to consider ALL possible combinations of the prime fac tors in order to get ALL pos si ble fac tors of 2,940.
We have 2^2 in our prime factorization, but the tricky thing is that we actually have THREE powers of 2 to con sider, namely 2^0, 2^1 and 2^2. This is because 2^0*3^1*5^1, for exam ple, is a fac tor of 2,940. We have to remem ber that there might be no fac tors of 2.
So, 2^2 yields three pos si ble pow ers of two.
We have 3^1 and 5^1. For each of those, two pow ers are involved (3^0 and 3^1, and also 5^0 and 5^1).
Finally, we have three for 7^2, namely 7^0, 7^1, and 7^2.
So, we can set up a visual rep re sen ta tion of pos si ble com bi na tions that yield a fac tor of 2,940:
2^_ * 3^_ * 5^_ * 7^_ (where each blank represents a possible exponent).
There are 3 pos si ble expo nents for the first blank, 2 for the sec ond, 2 for the third, and 3 for the fourth.
Total num ber of fac tors: 3*2*2*3 = 36.
And once again, the big takeaway:
Our prime fac tor iza tion was 2^2 * 3^1 * 5^1 * 7^2. All we need to do is add 1 to each expo nent and mul ti ply the results:
(2+1)*(1+1)*(1+1)*(2+1) = 3*2*2*3 = 36.
2,940 has a total of 36 factors.
It may take a minute (or twenty!) to wrap your head around the logic behind this method, but once you apply it, you’ll find there’s no bet ter strat egy. It’s quick, accu rate, and not very labor-intensive. It cer tainly beats writ ing out every factor!
Let’s try another one, so you can see how quick this can be:
540
5 * 108
5 * 2 * 54
5 * 2 * 2 * 27
5 * 2 * 2 * 3 * 3 * 3
Prime fac tor iza tion: 2^2 * 3^3 * 5^1
Num ber of fac tors: (2+1)*(3+1)*(1+1) = 3*4*2 = 24.
540 has 24 factors.
Now, apply what we’ve done (and more!) to some thought exercises:
1. Try this method with per fect squares. Notice any thing distinctive?
2. What type of num ber has exactly three fac tors? How about five?
3. How many num bers from 1 to 200 inclu sive have no more than three dis tinct prime fac tors? (For exam ple, 2^6 has only one dis tinct prime fac tor, namely 2.)
4. If you ran domly pick a num ber from 1 to 100 inclu sive, what is the prob a bil ity that you choose a num ber that has exactly six factors?
--
Rich Zwelling is one of the expert teach ers of Knewton’s GMAT course. He’s never been shy about pro fess ing his love for prime numbers.
