Pedros above has posted the most efficient way to check if a number is prime. In general, it is *very* time consuming to prove that a large number *is* prime -- so time consuming that you could never be asked to do it on the GMAT. It is, however, sometimes easy to see that a large number is *not* prime, and that is something you are occasionally asked to do on the test. So, for example, it is easy enough to see that none of the numbers
are prime; three of them are even, 31,113 is divisible by 3 (add the digits) and 31,115 is divisible by 5 (it ends in 5). However, it would take several minutes with pen and paper to work out whether 31,111 is prime (it is not, as it turns out; it is divisible by 53). The only way to check that is to start trying to divide it by small primes until you find a factor, and that takes ages; you don't have time to do that on the GMAT, so they can't ask you to do it. The only way the GMAT can ask you whether a large number is prime is if it is not prime, and in that case the number must have an 'obvious' factor like 2, 3, or 5, or a factor you can find using algebraic techniques, as in the following examples:
11! + 7 (since 11! and 7 are both multiples of 7, when we add them we must get a multiple of 7, so 11! + 7 is not prime)
13^9 + 13^2 + 13 (again, we are adding multiples of 13, so we must get a multiple of 13; 13^9 + 13^2 + 13 is not prime)
1003^2 - 1000^2 (this follows the 'difference of squares' pattern, so we can factor: 1003^2 - 1000^2 = (1003+1000)(1003-1000) = (2003)(3), so is not a prime number)
Nov 2011: After years of development, I am now making my advanced Quant books and high-level problem sets available for sale. Contact me at ianstewartgmat at gmail.com for details.
Private GMAT Tutor based in Toronto