• Foundation
  • About 15 min
  • 5 practice questions

Listing the divisors of a number: names, lists and tracing

Write the algorithm that lists the divisors of a number, execute it step by step while tracking a list, and use it to build a test for whether a number is prime.

If something looks wrong, please tell us.

By the end of this lesson you can

  • Write the algorithm divisors(n) using a list and a named counter j.
  • Execute (trace) the algorithm by hand, writing the list after each step.
  • Use divisors(n) to write an algorithm prime(n) that decides whether n is prime.

The next few lessons work towards an algorithm for the greatest common divisor (gcd), also called the highest common factor (HCF). A good way to design an algorithm is to break the problem into smaller problems we can already solve. The gcd needs the divisors of each number, so we begin there.

The algorithm divisors(n)

Every divisor (factor) of n lies between 1 and n. The simplest method is to try each of these numbers in turn. We must also remember the divisors we find, so we keep them in a list, written in square brackets, such as [1, 2, 4]. At the start we know no divisors, so the list is empty, [ ]. Each new divisor is added at the end.

  1. Start with an empty list called list-of-divisors.
  2. For each number j in 1, 2, 3, ..., n: if j divides n, add j to the end of list-of-divisors.
  3. Report list-of-divisors.

Notice the names. 'list-of-divisors' and 'j' let us refer to values that change as the algorithm runs. Without a name for 'the number being tried now', it would be clumsy to say what to do with it. The basic step we assume we can do is deciding whether a smaller number divides a larger one.

Worked example 1: executing divisors(20)

Tracing divisors(20)
jDoes j divide 20?list-of-divisors after this step
(start)-[ ]
1Yes[1]
2Yes[1, 2]
3No[1, 2]
4Yes[1, 2, 4]
5Yes[1, 2, 4, 5]
6 to 9No[1, 2, 4, 5]
10Yes[1, 2, 4, 5, 10]
11 to 19No[1, 2, 4, 5, 10]
20Yes[1, 2, 4, 5, 10, 20]

Running through an algorithm like this is called executing or tracing it. The result is divisors(20) = [1, 2, 4, 5, 10, 20]. Because j was tried in order from 1 upwards, the list comes out in increasing order, a fact we will use in the next lesson. The algorithm checked 20 values of j; for any n it checks n values, so a bigger n means more work.

The building blocks of an algorithm

What divisors(n) is made of

  • Basic step
    • Does j divide n?
  • Repetition
    • For each j in 1, 2, ..., n
  • Condition
    • Add j only if j divides n
  • Names and data
    • j: the number being tried
    • list-of-divisors: a list that grows

divisors(n): start with an empty list; for each j from 1 to n, if j divides n, add j to the list. The list comes out in increasing order.

Using one algorithm inside another: prime(n)

A prime number has exactly two different divisors, 1 and itself. So once we can compute divisors(n), testing for a prime is easy:

1. Let D be the list divisors(n).
2. If D has exactly 2 entries, report 'prime'; otherwise report 'not prime'.

This rule correctly reports that 1 is not prime, because divisors(1) = [1] has only one entry.

Worked example 2: is 21 prime? is 13 prime?

divisors(21): try j = 1 to 21. Divisors found: 1, 3, 7, 21. D = [1, 3, 7, 21] has 4 entries, so 21 is not prime (21 = 3 × 7).

divisors(13): only 1 and 13 divide 13. D = [1, 13] has exactly 2 entries, so 13 is prime.

Worked example 3: divisors(28)

j = 1, 2 and 4 divide 28 (28 = 1 × 28 = 2 × 14 = 4 × 7). j = 3, 5 and 6 do not. j = 7 divides (7 × 4 = 28). j = 8 to 13 do not. j = 14 divides (14 × 2 = 28). j = 15 to 27 do not. j = 28 divides.
Result: [1, 2, 4, 7, 14, 28]. It has 6 entries, so 28 is not prime. (Notice that the divisors come in pairs, (1, 28), (2, 14) and (4, 7), an idea that can be used to save work.)

Key takeaways

  • divisors(n) tries every j from 1 to n and keeps the ones that divide n in a list.
  • Names such as j and list-of-divisors make an algorithm easy to state and to trace.
  • Algorithms combine basic steps, repetition ('for each') and conditions ('if').
  • One algorithm can use another: prime(n) checks whether divisors(n) has exactly 2 entries.

Check your understanding

  1. 1. What list does divisors(30) produce?

    1. [1, 2, 3, 5, 30]
    2. [2, 3, 5, 6, 10, 15]
    3. [1, 2, 3, 5, 6, 10, 15, 30]
    4. [30, 15, 10, 6, 5, 3, 2, 1]
    Show answer

    Answer: C. Trying j = 1 to 30 in order, the divisors found are 1, 2, 3, 5, 6, 10, 15 and 30, and they are added in that increasing order. The list includes both 1 and 30 itself.

  2. 2. While executing divisors(18), what is list-of-divisors just after j = 6 has been checked?

    1. [1, 2, 3, 6]
    2. [1, 2, 3]
    3. [1, 2, 3, 6, 9, 18]
    4. [6]
    Show answer

    Answer: A. j = 1, 2 and 3 divide 18; j = 4 and 5 do not; j = 6 does. So after j = 6 the list is [1, 2, 3, 6]. 9 and 18 are added only later.

  3. 3. How many values of j does divisors(375) check?

    1. 8
    2. 375
    3. 187
    4. 20
    Show answer

    Answer: B. The algorithm tries every j from 1 to n, so for n = 375 it checks 375 values, even though only 8 of them turn out to be divisors.

  4. 4. Using D = divisors(n), which rule correctly decides whether n is prime?

    1. n is prime if D contains 1
    2. n is prime if D has an odd number of entries
    3. n is prime if n is the last entry of D
    4. n is prime if D has exactly 2 entries
    Show answer

    Answer: D. A prime has exactly two divisors, 1 and itself, so D has exactly 2 entries. Every D contains 1 and ends with n, so those tests say nothing; and an odd count means a perfect square, not a prime.

  5. 5. Which part of divisors(n) is a conditional step?

    1. Start with an empty list
    2. If j divides n, add j to the list
    3. For each j in 1, 2, ..., n
    4. Report the list
    Show answer

    Answer: B. A conditional step is carried out only when a condition holds. 'Add j' happens only if j divides n. 'For each j' is the repetition, and the other two steps always happen.

Privacy · Terms · Refunds · Delivery