{"id":2853,"date":"2012-02-14T07:27:16","date_gmt":"2012-02-14T12:27:16","guid":{"rendered":"http:\/\/www.manhattanprep.com\/gre\/blog\/?p=2853"},"modified":"2019-08-30T16:45:14","modified_gmt":"2019-08-30T16:45:14","slug":"prime-explosion-breaking-numbers-into-primes","status":"publish","type":"post","link":"https:\/\/www.manhattanprep.com\/gre\/blog\/prime-explosion-breaking-numbers-into-primes\/","title":{"rendered":"Prime Explosion: Breaking Numbers Into Primes"},"content":{"rendered":"

This comic from XKCD<\/a> is making a very nerdy joke:<\/p>\n

<\/p>\n

The 70, upon opening a package, is “exploded” — into its prime factors.<\/p>\n

<\/p>\n

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:<\/p>\n

How many odd factors does 406 have?<\/p><\/blockquote>\n

Surely, you could approach this problem by listing all the factors of 406, preferably in pairs, so you don’t miss anything:<\/p>\n

\n1, 406
\n2, 203
\n(Hmmn, what do I try now? 3, 4, 5, and 6 don’t go in…)<\/em>
\n7, 58
\n(Okay … do I just keep plugging stuff into the calculator? This is slow.)<\/em>
\n14, 29
\n(I think we’re done! At least, I can’t find any more! Um…)<\/em>\n<\/p><\/blockquote>\n

See, this is maybe not the best method. Instead, make a prime tree:<\/p>\n

\"tree\"<\/p>\n

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<\/em> 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!<\/p>\n

Prime trees are usually pretty fast and easy, even with big numbers.<\/p>\n

So, back to the question — how many odd factors does 406 have?<\/p>\n

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.<\/p>\n

The answer is 4. (That is, 403 has 4 odd factors, which just happen to be 1, 7, 29, and 203).<\/p>\n

Not so bad, right? Of course, this problem could be solved without primes, but some other questions specifically ask about primes. For instance:<\/p>\n

How many prime factors does 96 have?<\/p><\/blockquote>\n

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.<\/p>\n

Read carefully, though — if I asked how many distinct<\/em> prime factors, you’d say 2, not 6 (“distinct” means “different from each other,” so don’t count the “repeats”).<\/p>\n

You can find more problems on this topic in our Number Properties<\/em> book!<\/p>\n","protected":false},"excerpt":{"rendered":"

This comic from XKCD is making a very nerdy joke: The 70, upon opening a package, is “exploded” — into its prime factors.<\/p>\n","protected":false},"author":22,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,9,10],"tags":[],"yst_prominent_words":[],"class_list":["post-2853","post","type-post","status-publish","format-standard","hentry","category-gre-strategies","category-math-gre-strategies","category-gre-basic-math"],"_links":{"self":[{"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/posts\/2853","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/users\/22"}],"replies":[{"embeddable":true,"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/comments?post=2853"}],"version-history":[{"count":1,"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/posts\/2853\/revisions"}],"predecessor-version":[{"id":7168,"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/posts\/2853\/revisions\/7168"}],"wp:attachment":[{"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/media?parent=2853"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/categories?post=2853"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/tags?post=2853"},{"taxonomy":"yst_prominent_words","embeddable":true,"href":"https:\/\/www.manhattanprep.com\/gre\/wp-json\/wp\/v2\/yst_prominent_words?post=2853"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}