0
$\begingroup$

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.

  • 0
    In 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 3

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

  • 2
    Moreover, 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.