Last updated at October 28, 2026 by Teachoo
Transcript
Computing the Divisors of a Number Suppose we want to find all divisors of 18 . Any positive divisor must lie between 1 and 18. A number greater than 18 cannot divide 18 into a positive whole-number quotient. The simplest approach is therefore: Check every integer from 1 to 18, keeping the ones that divide 18 exactly. We need somewhere to keep the results. The chapter uses a list. A list is written using square brackets: [1, 2, 3] An empty list is: [] Algorithm to find the divisors of π Start with an empty list-of-divisors. For each number π in the sequence 1,2,3,β¦,π : If π divides π, add π to the end of list-of-divisors. Report the completed list. Here: π is the number whose divisors we want. π is the candidate currently being checked. list-of-divisors stores the divisors found so far. The name π does not have a special mathematical meaning here. It is simply a convenient name for the changing candidate. Executing the algorithm for 18 Following an algorithm step by step is called executing it. Algorithm to find the divisors of π Here: π is the number whose divisors we want. π is the candidate currently being checked. list-of-divisors stores the divisors found so far. The name π does not have a special mathematical meaning here. It is simply a convenient name for the changing candidate. Executing the algorithm for 18 Following an algorithm step by step is called executing it. Algorithm to find the divisors of π Start with an empty list-of-divisors For each number π in the sequence 1, 2, 3,β¦,π If π divides π, add π to the end of list-of-divisors Report the completed list. Executing the algorithm for 18 Following an algorithm step by step is called executing it. Candidate j | Does it divide 18? | List after checking 1 | Yes: (18)/(1)=18 | [1] 2 | Yes: (18)/(2)=9 | [1, 2] 3 | Yes: (18)/(3)=6 | [1, 2, 3] 4 | No | [1, 2, 3] 5 | No | [1, 2, 3] 6 | Yes: (18)/(6)=3 | [1, 2, 3, 6] 7,8 | No | [1, 2, 3, 6] 9 | Yes: (18)/(9)=2 | [1, 2, 3, 6, 9] 10 to 17 | No | Unchanged 18 | Yes: (18)/(18)=1 | [1, 2, 3, 6, 9, 18] Candidate j | Does it divide 18? | List after checking 1 | | [1] 2 | | [1, 2] 3 | | [1, 2, 3] 4 | No | [1, 2, 3] 5 | No | [1, 2, 3] 6 | | [1, 2, 3, 6] 7,8 | No | [1, 2, 3, 6] 9 | | [1, 2, 3, 6, 9] 10 to 17 | No | Unchanged 18 | | [1, 2, 3, 6, 9, 18] Thus: divisors(18)=[π, π, π, π, π, ππ] Note: Numbers which fail the divisibility test are still checked, but are not stored Why is the list in increasing order? We examine candidates in this order: 1, 2, 3,β¦,18 Each new divisor is therefore greater than the divisors already recorded. Appending it to the end preserves increasing order. Why does this algorithm work? Every possible positive divisor lies between 1 and π, so none is missed. A number is added only if it divides π, so no incorrect entry is included. There are only π candidates, so the process stops. What basic operation does it assume? It assumes we already know how to check whether one number divides another exactly. For example To test 5 as a divisor of 18: (18)/(5)=3(3)/(5) Since the remainder is not zero, we reject 5 A number is added only if it divides π, so no incorrect entry is included. There are only π candidates, so the process stops. What basic operation does it assume? It assumes we already know how to check whether one number divides another exactly. For example To test 5 as a divisor of 18: (18)/(5)=3(3)/(5) Since the remainder is not zero, we reject 5 Letβs look at more examples