Prime Explosion: Breaking Numbers Into Primes
This comic from XKCD is making a very nerdy joke:
The 70, upon opening a package, is “exploded” — into its prime factors.
Breaking a number into prime factors can be very useful for problems we here at Manhattan GRE would categorize as “Primes and Divisibility” problems. For instance:
How many odd factors does 406 have?
Surely, you could approach this problem by listing all the factors of 406, preferably in pairs, so you don’t miss anything:
1, 406
2, 203
(Hmmn, what do I try now? 3, 4, 5, and 6 don’t go in…)
7, 58
(Okay … do I just keep plugging stuff into the calculator? This is slow.)
14, 29
(I think we’re done! At least, I can’t find any more! Um…)
See, this is maybe not the best method. Instead, make a prime tree:
That was much easier! All I did was cut 406 in half (any time a number is even, I’ll just divide by 2 as many times as I can), and then try other primes, in order, in my calculator — 3 didn’t go in to 203, 5 obviously doesn’t go in, 7 did go in — not only that, but when I divided 203 by 7 I got 29, which is also prime, so I knew I was done!
Prime trees are usually pretty fast and easy, even with big numbers.
So, back to the question — how many odd factors does 406 have?
Well, I can see from the tree that there’s 7 and 29. Also, 1 goes into every integer. We also have to count every odd factor we can make by multiplying the prime factors. Here, that’s just 7 x 29 = 203, which is odd.
The answer is 4. (That is, 403 has 4 odd factors, which just happen to be 1, 7, 29, and 203).
Not so bad, right? Of course, this problem could be solved without primes, but some other questions specifically ask about primes. For instance:
How many prime factors does 96 have?
Make a tree and you’ll see that the prime factors of 96 are 2, 2, 2, 2, 2, and 3. So, 6 prime factors. Easy enough.
Read carefully, though — if I asked how many distinct prime factors, you’d say 2, not 6 (“distinct” means “different from each other,” so don’t count the “repeats”).
You can find more problems on this topic in our Number Properties book!