billzhao wrote:Is there a method to identify whether a certain number is prime number or not?
For example: 3217, 4999
Thanks!
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.
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.
