BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem
TTP OnDemand GMAT Video Course
Featured Course

Target Test Prep GMAT OnDemand

Scott Woodbury-Stewart’s private virtual classroom — 400 hours of master-class video lessons for the GMAT Focus Edition.

  • 715+ score guarantee — highest in the industry (99th percentile)
  • 52 chapters · 1,500+ lessons · 4,000+ practice questions
  • 400 hours of video · 1,500+ instructor-led HD smartboard lessons
  • 300,000+ students accepted to Harvard, Stanford, Wharton, Booth & Sloan & more
  • 24/7 live support + weekly Zoom office hours with GMAT instructors
  • TTP AI Assist — 24/7 AI-powered virtual tutor for instant help
  • 1,200+ flashcards + AI-powered study assistant & daily calendar
  • OnDemand, LiveTeach & GMAT Bootcamp formats available
  • Also: GRE, SAT Math & Executive Assessment courses
  • MBA Admissions Consulting now available
  • 🏆 2025 EdTech Breakthrough Award: Test Prep Solution Provider of the Year
  • 200,000+ students served
  • 5-day free trial — $0 to start, no auto-billing, cancel anytime
★★★★★ 5.0 (559 reviews)
130-pt guarantee
$0 to start then $127/mo
Start Free 5-Day Trial Read 559 Reviews →

How do you quickly find prime factors of a large number

Expert replies
Post new topic Post Reply
Previous Topic Next Topic
User avatar
Senior | Next Rank: 100 Posts
Posts: 58
Joined: Mon Nov 07, 2011 7:44 pm
Location: Washington DC
Thanked: 1 times
by iwillsurvive101 » Mon Nov 28, 2011 6:11 am
I got stuck finding prime factors of 5304. I have noticed that I repeatedly get stuck finding prime factors of "awkward" numbers, and it seems that its pretty common on advanced questions 650+....is there a short cut that you guys recommend?
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY
Source: — Problem Solving |
User avatar
Community Manager
Posts: 1060
Joined: Fri May 13, 2011 6:46 amFollowed by: 52 members
Location: Utrecht, The Netherlands
Thanked: 318 times

by neelgandham » Mon Nov 28, 2011 7:00 am
5304 -From the first glance, one can tell that the number is divisible by 3(sum of digits 5+3+4 is divisible by 3) and by 8 (The number formed with the last 3 digits -304 is divisible by 8). So, we know that 5304 = n*3*8 where n is a positive integer

5304 = n*3*8
1768 = n*8 (Divide both sides by 3)
221 = n (Divide both sides by 8)
Is 221 a prime number ?

196<221<225, 14^2<221<15^2.So you got to check if 221 is divisible by any number less than 15. Yes it is, divisible by 13(221=13*17). If you already know that 13 and 17 are prime numbers, you can stop here, else you can check if the numbers 13 and 17 are prime.

9<13<16, 3^2<13<4^2. So you got to check if 13 is divisible by any number less than 4, and No, there is no number which is a factor of 13.
16<17<25, 4^2<17<5^2. So you got to check if 17 is divisible by any number less than 4, and No, there is no number which is a factor of 17.

5304 = 3*8*13*17. So, 3,8,13,and 17 are prime factors of 5304.

p.s: Do you know that the largest KNOWN prime number is 2^(43,112,609)-1
Last edited by neelgandham on Mon Nov 28, 2011 8:15 am, edited 1 time in total.
Anil Gandham
Welcome to BEATtheGMAT | Photography | Getting Started | BTG Community rules | MBA Watch
Check out GMAT Prep Now's online course at https://www.gmatprepnow.com/
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2623
Joined: Mon Jun 02, 2008 3:17 amFollowed by: 355 members
Location: Montreal
Thanked: 1090 times
GMAT Score:780

by Ian Stewart » Mon Nov 28, 2011 8:09 am
iwillsurvive101 wrote:I got stuck finding prime factors of 5304. I have noticed that I repeatedly get stuck finding prime factors of "awkward" numbers, and it seems that its pretty common on advanced questions 650+....is there a short cut that you guys recommend?
You really can't be asked to find prime factors of 'awkward' large numbers on the GMAT, because it just takes far too long. The only large numbers that can be prime factorized in any reasonable amount of time are numbers which are divisible by 2, 3 and/or 5, since we have quick tests that let us see when a number is divisible by those three primes. So you could, perhaps, be asked to prime factorize a number like 3105, because you can quickly tell that you can divide by 5 and also by 9 (summing the digits), and therefore quickly get down to a much smaller number. You could never be asked to prime factorize a number like 12,121, though, since that number has no obvious prime divisors - all you could do is try dividing by 7, by 11, by 13, and so on, hoping to find a prime factor, and that would takes ages to do (don't waste your time doing it, but it is equal to 17*23*31). If you've seen questions which require you to prime factorize 'awkward' numbers, they are certainly prep company questions, and not official ones.

neelgandham wrote:
p.s: Do you know that the largest prime number is 2^(43,112,609)-1
There are infinitely many primes - there can't possibly be a largest prime number. That may be the largest known prime, however.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY
User avatar
Community Manager
Posts: 1060
Joined: Fri May 13, 2011 6:46 amFollowed by: 52 members
Location: Utrecht, The Netherlands
Thanked: 318 times

by neelgandham » Mon Nov 28, 2011 8:15 am
Ian Stewart wrote:
neelgandham wrote:
p.s: Do you know that the largest prime number is 2^(43,112,609)-1
There are infinitely many primes - there can't possibly be a largest prime number. That may be the largest known prime, however.
:banghead: Thanks for correcting! I meant 'Do you know that the largest KNOWN prime number is 2^(43,112,609)-1'. I have updated the post now :)
Anil Gandham
Welcome to BEATtheGMAT | Photography | Getting Started | BTG Community rules | MBA Watch
Check out GMAT Prep Now's online course at https://www.gmatprepnow.com/
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY
User avatar
Senior | Next Rank: 100 Posts
Posts: 58
Joined: Mon Nov 07, 2011 7:44 pm
Location: Washington DC
Thanked: 1 times

by iwillsurvive101 » Mon Nov 28, 2011 9:19 am
neelgandham wrote: p.s: Do you know that the largest KNOWN prime number is 2^(43,112,609)-1
Hey - Where did you get this from?
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY
User avatar
Senior | Next Rank: 100 Posts
Posts: 58
Joined: Mon Nov 07, 2011 7:44 pm
Location: Washington DC
Thanked: 1 times

by iwillsurvive101 » Mon Nov 28, 2011 9:20 am
ah.. nevermind, just saw your update. Thank you guys!
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY
User avatar
GMAT Instructor
Posts: 509
Joined: Wed Apr 21, 2010 1:08 pmFollowed by: 85 members
Location: Irvine, CA
Thanked: 199 times
GMAT Score:750

by tpr-becky » Mon Nov 28, 2011 11:13 am
I always work a factor tree and start with the most obvious factor first, to do this you have to memorize your rules of divisibilty and know them very well.

For instance 5304 has a 4 as a factor (becuase the 04 is divisible by 4) or it has 2 as a factor or it has three - because the digits add up to 12, which is divible by 3.

5304/ 4 = 1326 - which has 2 and 3 as factors 1326/3 = 442 - which has 2 as a factor 442/2= 221 - have to check prime - not even, so not 2, 3, 4, 6, 8, 10, 12 or 14 (To be divisible by any even you must be even) not 5 (doesn't end in 5 or 0) Not 10 (doesn't end in 0) - so you have to check 7, 8, 11, and 13 - it is divisible by 13 and the result is 17.

So the end is that finding prime factors of large nubmers is common on GMAT and relies on your knowledge of divisibility and ability to do small division quickly and acurately - Think of using factor trees to keep your work orderly.
Becky
Master GMAT Instructor
The Princeton Review
Irvine, CA
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY
Master | Next Rank: 500 Posts
Posts: 124
Joined: Mon Jun 16, 2008 11:07 amFollowed by: 14 members
Thanked: 21 times
GMAT Score:750

by CappyAA » Mon Nov 28, 2011 11:18 am
+1 for a factor tree.

For me, it's usually much easier to start with the super easy prime factors. I keep dividing by 2 until I no longer have an even number. I then divide by 3 (you can check if the digits add up to a number divisible by 3). Then 5, etc.

As was previously mentioned, the GMAT generally won't give you extremely difficult factors. Usually the largest primes you'll have to check for are 13 or 17. So if you factor out properly on the front end, the number should be small enough by the time you have to deal with the awkward prime.
Taking the GMAT Again...PhD this time!

October 2008 Score: GMAT - 750 (50 Q, 41 V) :D

Manhattan GMAT 1 - 11/20/11 - 750 (50 Q, 42 V)
Manhattan GMAT 2 - 12/3/11 - 780 (51 Q, 45 V)
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2623
Joined: Mon Jun 02, 2008 3:17 amFollowed by: 355 members
Location: Montreal
Thanked: 1090 times
GMAT Score:780

by Ian Stewart » Mon Nov 28, 2011 6:45 pm
tpr-becky wrote: finding prime factors of large nubmers is common on GMAT
This isn't true in my experience. I've seen many thousand official GMAT questions, and I'm almost certain the largest actual number I've ever needed to prime factorize was 441 (in a PS question in OG11).

What you do often need to do is prime factorize expressions which represent large numbers - expressions like 3^29 - 3^27 - but in those cases, you are using algebraic factorization techniques, and not long division.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com
Top
Join the discussion
Log in to postLogin with Googleuse password
QUOTE IN REPLY
Post new topic Post Reply
• Page 1 of 1