It is currently 17 Oct 2017, 02:56

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# Prime Numbers

Author Message
TAGS:

### Hide Tags

Manager
Joined: 14 Jul 2009
Posts: 61

Kudos [?]: 1 [0], given: 3

### Show Tags

08 Feb 2010, 11:23
Hi all,

What is the fastest way to determine if a number is prime? I see some questions in which you need to check if a number is prime or not. The problem is sometimes the number is a huge number.

Thanks

Kudos [?]: 1 [0], given: 3

Intern
Joined: 16 May 2009
Posts: 28

Kudos [?]: 66 [0], given: 3

### Show Tags

08 Feb 2010, 11:42
GS has posted the answer to this question on his flash cards so credit goes to him/her.

How to determine prime no = Find approx square root of the number. Then check if all the prime
numbers below the square root are factors of the given number. If none are then the number is
prime else not.
e.g. number 91. approx sq root is 10
Prime number below 10 are 2.3.5&7.
91 is not divisible by2,3 or 5. But it is divisible by 7.
Therefore 91 is not prime

Kudos [?]: 66 [0], given: 3

GMAT Tutor
Joined: 24 Jun 2008
Posts: 1339

Kudos [?]: 1951 [1], given: 6

### Show Tags

08 Feb 2010, 15:32
1
KUDOS
Expert's post
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

31,112
31,113
31,114
31,115
31,116

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)
_________________

GMAT Tutor in Toronto

If you are looking for online GMAT math tutoring, or if you are interested in buying my advanced Quant books and problem sets, please contact me at ianstewartgmat at gmail.com

Kudos [?]: 1951 [1], given: 6

Intern
Joined: 16 May 2009
Posts: 28

Kudos [?]: 66 [0], given: 3

### Show Tags

08 Feb 2010, 15:57
IanStewart wrote:

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)

Thank you Ian for that analysis

Kudos [?]: 66 [0], given: 3

Re: Prime Numbers   [#permalink] 08 Feb 2010, 15:57
Display posts from previous: Sort by