Write an algorithm prime(n) to check if n is prime.
(Hint: A prime number p has exactly two distinct factors, 1 and p. Can you make use of divisors(n) to write out prime(n)?)
Answer: prime(n): compute divisors(n); if the list has exactly two numbers, report “n is prime”, otherwise report “n is not prime”. E.g. divisors(13) = [1, 13] → prime; divisors(15) = [1, 3, 5, 15] → not prime.
Step-by-step solution
Idea: A prime has exactly two divisors, 1 and itself. The divisors algorithm already gives the full list of divisors, so we only need to count them.
- Algorithm prime(n)
1. Let divisors-of-n be the list obtained by computing divisors(n).
2. If divisors-of-n has exactly two elements, report “n is prime”.
3. Otherwise, report “n is not prime”.1½ marks - Why it is correct: every n ≥ 2 has at least the two divisors 1 and n. It is prime exactly when there are no others, that is, when the list has exactly two elements. For n = 1 the list is [1], one element, so 1 is correctly reported as not prime.1 mark
- Examples: divisors(13) = [1, 13], two elements → 13 is prime. divisors(15) = [1, 3, 5, 15], four elements → 15 is not prime.½ mark
- A quicker version: we can stop as soon as one divisor j with 2 ≤ j < n is found (then n is not prime), and by the pairs idea we only need to try j up to √n.
prime(n): compute divisors(n); report “prime” if the list has exactly two elements, and “not prime” otherwise.
Answer to write in the exam
Algorithm prime(n):
1. divisors-of-n = divisors(n)
2. If divisors-of-n has exactly 2 elements, report “n is prime”
3. Otherwise, report “n is not prime”
e.g. divisors(13) = [1, 13] → prime; divisors(15) = [1, 3, 5, 15] → not prime
∴ n is prime ⇔ divisors(n) has exactly two elements.
Common mistakes that cost marks
- Testing “is 1 in the list and is n in the list”. That is true for every number, so it cannot detect primes.
- Reporting 1 as prime. divisors(1) = [1] has only one element, so 1 is not prime.
- Writing “if n has no factors, it is prime”; every number has the factors 1 and n.
How this can come in the exam
MCQ (1 mark)
prime(n) computes divisors(n). For n = 91, how many elements does this list have?
- 2
- 3
- 4
- 6
Show answer
(C) 4
91 = 7 × 13, so divisors(91) = [1, 7, 13, 91]: 4 elements, and 91 is not prime.
Try one yourself
Execute prime(n) for n = 29 and n = 51.
Show answer
divisors(29) = [1, 29], two elements: 29 is prime. divisors(51) = [1, 3, 17, 51], four elements: 51 is not prime.
More questions like this
- Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.
(Hint: Compute divisors(n) and then filter out the primes in this list.) - We can also find the gcd of two numbers by computing prime factorisation of both the numbers. Try to write an algorithm to compute the prime factorisation of a number.
- These days the word ‘algorithm’ pops up everywhere. What exactly is an algorithm? What does it have to do with mathematics?
- Add two 4-digit numbers using the steps we have written down. Make sure you follow the steps precisely; do not perform any action that is not explicitly mentioned. Are you able to obtain the correct result?
- What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?