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.)
Answer: Start with an empty list prime-divisors; for each x in divisors(n), if prime(x) says x is prime, add x; report prime-divisors. E.g. primedivisors(60) = [2, 3, 5].
Step-by-step solution
Idea: Combine two algorithms we already have: divisors(n) lists every divisor, and prime(x) tells us whether x is prime. Keep only the divisors that pass the prime test.
- Algorithm primedivisors(n)
1. Start with an empty list prime-divisors.
2. Let divisors-of-n be the list obtained by computing divisors(n).
3. For each number x in divisors-of-n:
– if prime(x) reports that x is prime, add x to prime-divisors.
4. Report prime-divisors.1½ marks - Execute for n = 60: divisors(60) = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60].½ mark
- Test each: 1 is not prime (one divisor); 2, 3 and 5 are prime; 4, 6, 10, 12, 15, 20, 30, 60 have more than two divisors, so they are not prime. So primedivisors(60) = [2, 3, 5].½ mark
- The answer list is in increasing order, because divisors(n) is in increasing order and we keep the order. 1 is never included, since 1 is not prime.½ mark
primedivisors(n): start with an empty list; for each x in divisors(n), add x if prime(x) says it is prime; report the list. For example primedivisors(60) = [2, 3, 5].
Answer to write in the exam
Algorithm primedivisors(n):
1. prime-divisors = [ ]
2. divisors-of-n = divisors(n)
3. For each x in divisors-of-n: if prime(x), add x to prime-divisors
4. Report prime-divisors
e.g. divisors(60) = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60] → keep 2, 3, 5
∴ primedivisors(60) = [2, 3, 5]
Common mistakes that cost marks
- Including 1 in the list of prime divisors. 1 is not a prime number.
- Including n itself when n is not prime (60 is a divisor of 60 but is not prime). It belongs in the list only when n is prime.
- Listing prime factors with repeats (2, 2, 3, 5 for 60). The question asks for the list of prime divisors, each once.
How this can come in the exam
MCQ (1 mark)
primedivisors(90) is
- [2, 3, 5]
- [2, 3, 5, 9]
- [1, 2, 3, 5]
- [2, 5]
Show answer
(A) [2, 3, 5]
90 = 2 × 32 × 5. Its prime divisors are 2, 3 and 5; 9 is not prime and 1 is not prime.
Try one yourself
Execute primedivisors(105).
Show answer
divisors(105) = [1, 3, 5, 7, 15, 21, 35, 105]. Keeping only primes: [3, 5, 7].
More questions like this
- 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?
- Why is it important to align the columns from right to left?