SMC 2007 Q16
16. Damien wishes to find out if 457 is a prime number. In order to do this he needs to check whether it is exactly divisible by some prime numbers. What is the smallest number of possible prime number divisors that Damien needs to check before he can be sure that 457 is a prime number?
- A 8
- B 9
- C 10
- D 11
- E 12
Senior Mathematical Challenge 2007, Question 16. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: A 8
The smallest number of possible prime divisors of 457 that Damien needs to check is the number of prime numbers less than or equal to the square root of 457. Since \(21^2 < 457 < 22^2\), he needs to check only primes less than 22. These primes are 2, 3, 5, 7, 11, 13, 17 and 19.
Solution © UK Mathematics Trust, from the SMC 2007 solutions.