Quick way to find a prime factor of a number ?

Expert replies

II: Master | Next Rank: 500 Posts; Posts: 400; Joined: Mon Dec 10, 2007 1:35 pm; Location: London, UK; Thanked: 19 times; GMAT Score:680

by II » Sun Mar 23, 2008 6:54 am

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.

Like this post

Source: Beat The GMAT — Problem Solving | Sun Mar 23, 2008 6:54 am

xilef: Master | Next Rank: 500 Posts; Posts: 111; Joined: Thu Jan 31, 2008 4:05 pmFollowed by: 1 member; Thanked: 18 times

by xilef » 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

Like this post

II: Master | Next Rank: 500 Posts; Posts: 400; Joined: Mon Dec 10, 2007 1:35 pm; Location: London, UK; Thanked: 19 times; GMAT Score:680

by II » 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.

Like this post

tmmyc: Senior | Next Rank: 100 Posts; Posts: 72; Joined: Mon Mar 10, 2008 10:29 am; Thanked: 25 times

by tmmyc » 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.

Like this post

Stuart@KaplanGMAT: GMAT Instructor; Posts: 3225; Joined: Tue Jan 08, 2008 2:40 pmFollowed by: 614 members; Location: Toronto; Thanked: 1710 times; GMAT Score:800

by Stuart@KaplanGMAT » 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.

Stuart Kovinsky | Kaplan GMAT Faculty | Toronto

Kaplan Exclusive: The Official Test Day Experience | Ready to Take a Free Practice Test? | Kaplan/Beat the GMAT Member Discount
BTG100 for $100 off a full course

Like this post

Bogussi: Newbie | Next Rank: 10 Posts; Posts: 1; Joined: Thu Dec 23, 2010 8:03 am

by Bogussi » 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:
https://www.math.com/school/subject1/pra ... Pract.html

Like this post

chakradhar143: Newbie | Next Rank: 10 Posts; Posts: 1; Joined: Tue Sep 03, 2013 11:45 am

by chakradhar143 » 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

Like this post

Post new topic Post Reply

• Page 1 of 1

GMAT Course Reviews

559 reviews

1168 reviews

431 reviews

359 reviews

147 reviews

5/5

5 Star (560 Reviews)

"Target Test Prep is the closest to the official version of the GMAT exam, about 99% accuracy in terms of the quality and quantity of information. The course has excellently created singular sets of focused lessons and tests for every possible topic that one could come across in the official GMAT exam."

"The TTP course maximizes the efficiency of the time you spend studying. It will take time and effort but I could almost guarantee that if you complete the course exactly as it is laid out you will get an amazing score. They also have a very responsive team willing to help with any questions you might have."

"TTP has two things that I think no other test prep company offers: A teaching approach that reinforces understanding and an attitude that will give you the mental preparedness needed to succeed on the test. TTP gives you a deep understanding of the concept you need to know while teaching you how to think."

Write a Review