Please help with this general quesiton.
This topic has expert replies
Source: Beat The GMAT — Quantitative Reasoning |
-
BlindVision
.gif)
- Master | Next Rank: 500 Posts
- Posts: 253
- Joined: Fri Dec 26, 2008 8:39 pm
- Thanked: 8 times
- Followed by:1 members
A Prime Number is divisible only by itself and one. My short method is to try factoring the number... if any extra numbers other than "itself" and "one" comes out, then it is not a Prime Number. Hope that helps!
GMAT/MBA Expert
-
Ian Stewart
- GMAT Instructor
- Posts: 2623
- Joined: Mon Jun 02, 2008 3:17 am
- Location: Montreal
- Thanked: 1090 times
- Followed by:355 members
- GMAT Score:780
It's sometimes easy to see that a large number is *not* prime, but it is extremely time consuming to prove that a large number *is* prime. So, for example, it's easy to see that none of the numbers from 3212 to 3216 is prime, at least if you know the simple divisibility tests (3212, 3214, and 3216 are all even; 3215 is divisible by 5; 3213 is divisible by 3). It's not at all easy, at least in two minutes, to see that 3217 *is* prime.billzhao wrote:Is there a method to identify whether a certain number is prime number or not?
For example: 3217, 4999
Thanks!
The most efficient method, in general, to prove a number is prime is the following, taking the number 3217 as an example. To prove 3217 is prime, you need to:
- estimate the square root of 3217 (which is roughly 57).
- try dividing 3217 by every prime less than the root of 3217 ~ 57. If 3217 is not divisible by any of these primes, then 3217 must be prime.
That is, we'd need to check whether 3217 can be divided by 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47, and 53. That's a lot of work! You'd never need to do that in a GMAT question, and there is no method that is generally more efficient.
In fact, internet encryption systems are based essentially on this fact -
that it's very time consuming to identify large primes and to factor large numbers (at least if the factors are large). So the reason you can send your bank details safely over the internet is because the process above (and related processes) take a long time if you're dealing with large numbers, even for a computer.
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
ianstewartgmat.com
