• e-gmat Exclusive Offer
    Get 300+ Practice Questions
    25 Video lessons and 6 Webinars for FREE

    Available with Beat the GMAT members only code

    MORE DETAILS
    e-gmat Exclusive Offer
  • Target Test Prep
    5-Day Free Trial
    5-day free, full-access trial TTP Quant

    Available with Beat the GMAT members only code

    MORE DETAILS
    Target Test Prep
  • Economist Test Prep
    Free Trial & Practice Exam
    BEAT THE GMAT EXCLUSIVE

    Available with Beat the GMAT members only code

    MORE DETAILS
    Economist Test Prep
  • Veritas Prep
    Free Veritas GMAT Class
    Experience Lesson 1 Live Free

    Available with Beat the GMAT members only code

    MORE DETAILS
    Veritas Prep
  • Magoosh
    Magoosh
    Study with Magoosh GMAT prep

    Available with Beat the GMAT members only code

    MORE DETAILS
    Magoosh
  • Kaplan Test Prep
    Free Practice Test & Review
    How would you score if you took the GMAT

    Available with Beat the GMAT members only code

    MORE DETAILS
    Kaplan Test Prep
  • PrepScholar GMAT
    5 Day FREE Trial
    Study Smarter, Not Harder

    Available with Beat the GMAT members only code

    MORE DETAILS
    PrepScholar GMAT
  • EMPOWERgmat Slider
    1 Hour Free
    BEAT THE GMAT EXCLUSIVE

    Available with Beat the GMAT members only code

    MORE DETAILS
    EMPOWERgmat Slider
  • Varsity Tutors
    Award-winning private GMAT tutoring
    Register now and save up to $200

    Available with Beat the GMAT members only code

    MORE DETAILS
    Varsity Tutors

Quick way to find a prime factor of a number ?

This topic has 1 expert reply and 5 member replies
II Master | Next Rank: 500 Posts
Joined
10 Dec 2007
Posted:
400 messages
Thanked:
19 times
Target GMAT Score:
700
GMAT Score:
680

Quick way to find a prime factor of a number ?

Post Sun Mar 23, 2008 6:54 am
Elapsed Time: 00:00
  • Lap #[LAPCOUNT] ([LAPTIME])
    How would you find the prime factors of 3841, for example ?
    Does anyone know of a quick way to do it.

    Thanks for the help. Appreciate it.

    Need free GMAT or MBA advice from an expert? Register for Beat The GMAT now and post your question in these forums!
    xilef Master | Next Rank: 500 Posts Default Avatar
    Joined
    31 Jan 2008
    Posted:
    111 messages
    Followed by:
    1 members
    Thanked:
    18 times
    Post Mon Mar 24, 2008 9:50 am
    You can start with the smallest prime factor and then use the divisibility rules:

    Divisibility Rules

    How do you know if a number is divisible by 2?

    If it's an even number

    How do you know if a number is divisible by 3?

    Sum of the digits is divisible by 3

    How do you know if a number is divisible by 4?

    Last two digits are divisible by 4

    How do you know if a number is divisible by 5?

    Last digit is either a 0 or a 5

    How do you know if a number is divisible by 6?

    Number is even and divisible by 3

    How do you know if a number is divisible by 7?

    Number divides evenly by 7 (there is no shortcut)

    How do you know if a number is divisible by 9?

    Sum of the digits is divisible by 9



    3841 seems to be prime

    If it was 3840:

    It's even, so divisible by 2
    now you have 1920 which is also divisible by 2
    960 divisible by 2
    480 divisible by 2
    240 divisible by 2
    120 divisible by 2
    60 divisible by 2
    30 divisible by 2
    15 is 3 *5

    so your prime factors are:

    2*2*2*2*2*2*2*2*3*5

    II Master | Next Rank: 500 Posts
    Joined
    10 Dec 2007
    Posted:
    400 messages
    Thanked:
    19 times
    Target GMAT Score:
    700
    GMAT Score:
    680
    Post Mon Mar 24, 2008 2:30 pm
    Hi There ... thanks for the info. I know this approach ... which is easy to use for numbers with prime factor between 1 and 10 ... as you can use the divisibility rules.

    However, I was interested in learning the quickest way to get to the prime factors of 3841 ... or identify that this was a prime number.

    To identify if 3841 is a prime number we can look at the nearest square number closest to (but lesser than) 3841.
    The nearest square, closest to (but lesser than) 3841 is 3721 (61 squared).
    We can then look at all the prime numbers under 61 and check if they are factors of 3841. If they are not, then 3841 is a prime number.

    I dont know if there is another quicker way ... of do I even need to be concerned with this ... do I need to be looking at doing this quicker ... is this going to be tested in the GMAT ???

    Thanks.

    tmmyc Senior | Next Rank: 100 Posts Default Avatar
    Joined
    10 Mar 2008
    Posted:
    72 messages
    Thanked:
    25 times
    Test Date:
    April 19, 2008
    Target GMAT Score:
    730
    Post Mon Mar 24, 2008 7:34 pm
    The most thorough way to test if a number such as 3841 is prime is to test its divisibility by all prime numbers between 1 and the sqrt(3841).

    sqrt(3841) is about 62.

    We don't need to test anything above 62 because any number above 62 would have to be multiplied by a number smaller than 62 to get to 3841, and we've already tested all the numbers smaller than 62.

    Therefore, we test: 2, 3, 5, 7, 11...
    We don't need to test 4, because checking 2 would have caught that. The same goes for 6 and 8. We don't need to test 9 because the 3 would have caught that, so on and so forth.

    We keep testing prime numbers until we find a factor or we hit 62.

    Therefore, we keep testing: 2, 3, 5, 7, 11, 13, 17, 19, 23
    Ah ha! We found one: 23*167 = 3841

    Performing the same test on 167, we learn that 167 is also prime. The prime factors of 3841 is therefore 23 and 167.

    Unforunately, I do not know a quicker approach to solving this.

    GMAT/MBA Expert

    Stuart Kovinsky GMAT Instructor
    Joined
    08 Jan 2008
    Posted:
    3225 messages
    Followed by:
    608 members
    Thanked:
    1710 times
    GMAT Score:
    800
    Post Tue Mar 25, 2008 11:46 am
    II wrote:
    I dont know if there is another quicker way ... of do I even need to be concerned with this ... do I need to be looking at doing this quicker ... is this going to be tested in the GMAT ???

    Thanks.
    You won't be tested on your ability to recognize whether or not huge numbers are primes or to find really big prime factors of numbers.

    Thanked by: GmatKiss
    Free GMAT Practice Test under Proctored Conditions! - Find a practice test near you or live and online in Kaplan's Classroom Anywhere environment. Register today!
    Bogussi Newbie | Next Rank: 10 Posts Default Avatar
    Joined
    23 Dec 2010
    Posted:
    1 messages
    Post Tue Dec 28, 2010 5:18 am
    II wrote:
    I dont know if there is another quicker way ...
    If anyone wants to improve through extensive practice, try this link:
    http://www.math.com/school/subject1/practice/S1U3L1/S1U3L1Pract.html

    chakradhar143 Newbie | Next Rank: 10 Posts Default Avatar
    Joined
    03 Sep 2013
    Posted:
    1 messages
    Post Tue Sep 03, 2013 11:48 am
    divide the number in two parts ex 360 =36*10 and then follow tree pattern
    i) 36 = 9*4 while 10 =2*5 ( here 2 and 5 are prime number so no worry)
    ii) 3*3 and 2*2( so you got 3 and 2 , which are prime numbers)
    now finally assembling the factors
    2*5*3*3*2*2

    Best Conversation Starters

    1 lheiannie07 111 topics
    2 ardz24 64 topics
    3 LUANDATO 62 topics
    4 swerve 60 topics
    5 AAPL 57 topics
    See More Top Beat The GMAT Members...

    Most Active Experts

    1 image description Brent@GMATPrepNow

    GMAT Prep Now Teacher

    160 posts
    2 image description EconomistGMATTutor

    The Economist GMAT Tutor

    130 posts
    3 image description Rich.C@EMPOWERgma...

    EMPOWERgmat

    122 posts
    4 image description GMATGuruNY

    The Princeton Review Teacher

    122 posts
    5 image description Scott@TargetTestPrep

    Target Test Prep

    118 posts
    See More Top Beat The GMAT Experts