Which of the following integers is prime: 187, 287, 387, 487, or 587? I can calculate it by hand, but that would take a long time. Is there an easier way? I noticed the numbers only differ 100 from each other, but can I use that fact? Exactly one of these must be prime.
Prime numbers: How would you do this efficiently?
0
$\begingroup$
elementary-number-theory
-
0In general, there is no efficient way to tell if a number is prime. It's always going to be a headache. Only 50 years ago, many introductory books on number theory had a table of primes in the back to help you solve problems like this. Ultimately the easiest way is to use one of the better algorithms on a computer. – 2013-10-29
3 Answers
6
187 is obviously a multiple of 11. 287 is obviously a multiple of 7. 387 is obviously a multiple of 3. So you just have to work on 487 and 587.
2
Also, if a number is not prime, one factor is always less than or equal to the square root of that number
For example, the square root of 487 is a little more than 22. So you need only check the primes below 22 (and you see immediately that 2,3 or 5 doesn't work, so you need only check 5 primes).
-
2Moreover, you don't have to try 7, since it divides 287 but not the difference between 487 and 287; for similar reasons, you don't have to check 11 or 17. Adding 13 to 487 gives 500, which is not a multiple of 13, so that's out. 57 is a multiple of 19, but 430 isn't, so 487 isn't. – 2012-01-31
0
All prime numbers are of the form (6n+1) or (6n-1). Dividing these numbers by 6 except
187, a multiple of 11
287, an obvious multiple of 7
387, a multiple of 9/3
487 gives a remainder 1, as well as 587 giving a remainder of -1, we can conclude that both of them are prime.