Algorithms · 2 marks

Algorithm to find the divisors of n: 1. Start with an empty list-of-divisors. 2. For each number j in the sequence 1, 2, 3, …, n – if j divides n, add j to the list-of-divisors. Let us execute this algorithm for a small number, say 18.

Answer: divisors(18) = [1, 2, 3, 6, 9, 18]. The list comes out in increasing order because the numbers are checked from 1 up to 18.

Step-by-step solution

Idea: Executing an algorithm means doing its steps one by one and writing down the value of every named quantity (here list-of-divisors) after each step. The only basic step needed is knowing whether one number divides another.

Start: list-of-divisors = [ ] (empty).
j = 1: 1 divides 18 → [1]. j = 2: divides → [1, 2]. j = 3: divides → [1, 2, 3].
j = 4, 5: do not divide 18 → list unchanged, [1, 2, 3].½ mark
j = 6: divides → [1, 2, 3, 6]. j = 7, 8: do not divide → unchanged.
j = 9: divides → [1, 2, 3, 6, 9].½ mark
j = 10, 11, …, 17: none divides 18 → unchanged.
j = 18: divides → [1, 2, 3, 6, 9, 18]. The scan is over.½ mark
So divisors(18) = [1, 2, 3, 6, 9, 18]. The list is in increasing order because the values of j were checked in order from 1 to 18. The basic step assumed is that we can tell whether a smaller number divides a larger one.½ mark

divisors(18) = [1, 2, 3, 6, 9, 18], in increasing order.

Check: Divisors come in pairs with product 18: 1 × 18, 2 × 9, 3 × 6. That gives the same six numbers ✓.

Answer to write in the exam

list-of-divisors = [ ]

j = 1, 2, 3 divide 18 → [1, 2, 3]

j = 4, 5 do not divide → [1, 2, 3]

j = 6 divides → [1, 2, 3, 6]; j = 7, 8 do not divide

j = 9 divides → [1, 2, 3, 6, 9]; j = 10 to 17 do not divide

j = 18 divides → [1, 2, 3, 6, 9, 18]

∴ divisors(18) = [1, 2, 3, 6, 9, 18]

Common mistakes that cost marks

Leaving out 1 or 18 itself. Every number is divisible by 1 and by itself.
Stopping at 9 (half of 18) and forgetting to check j = 18.
Writing only the final list without showing how the list changes, when the question asks you to execute the algorithm.

How this can come in the exam

MCQ (1 mark)

The divisors algorithm is executed for n = 20. What is list-of-divisors just after j = 5 has been checked?

[1, 2, 4, 5]
[1, 2, 5]
[1, 2, 4, 5, 10, 20]
[2, 4, 5]

Show answer

(A) [1, 2, 4, 5]
1, 2, 4 and 5 divide 20 and 3 does not. Later numbers (10, 20) have not been checked yet.

Try one yourself

Execute the divisors algorithm for 28.