Is it a prime number?
Choose a number and watch a program try divisors 2, 3, 4 … with the remainder. It stops at the first divisor it finds, or as soon as the divisor times itself is bigger than the number. Count the tries and find out why it never needs to go further.
Core concept
A number is prime when only 1 and itself divide it; a program tests divisors with %, stops at the first one that divides, and only needs to try divisors up to the square root, because any bigger factor comes with a smaller partner
Topic: Algorithms
A prime number has exactly two factors: 1 and itself. 13 is prime; 21 is not, because 3 × 7 = 21. To test a number, a program tries divisors one by one: d = 2, 3, 4 … and checks number % d. If the remainder is 0, d divides the number, so it is not prime and the program can stop. But how far must it go? Factors come in pairs: 49 = 7 × 7 and 21 = 3 × 7. In every pair, one factor is at most the square root of the number. So if no divisor is found by the time d × d is bigger than the number, there is none, and the number is prime. The number 1 has only one factor, so it is not prime.
What you will learn
- Explain what a prime number is and why 1 is not prime.
- Trace a while loop that tests divisors with the remainder (%).
- Explain why testing divisors up to the square root is enough.
- Count the tries the algorithm needs for different numbers.
Before you start
- Know factors, multiples and remainders.
Materials
- A notebook to check divisions by hand
Equipment
- None
Procedure
- Test 21 and see which divisor the program finds.
- Test a prime such as 97 and count the divisors it tries.
- Test 1 and read why it is not prime.
- Answer the practice challenges.