Try to execute the algorithm to compute the divisors of 15, 135, and 775. How does the amount of work increase as the numbers grow?

Step-by-step solution

Idea: The algorithm tests j = 1, 2, 3, …, n, one at a time. So the number of tests equals n, however many divisors there turn out to be.

1. n = 15: check j = 1 to 15. 1, 3, 5, 15 divide 15 (2, 4, 6, … do not). divisors(15) = [1, 3, 5, 15].½ mark
2. n = 135: check j = 1 to 135. 135 = 3³ × 5, and the numbers that divide it are [1, 3, 5, 9, 15, 27, 45, 135].½ mark
3. n = 775: check j = 1 to 775. 775 = 5² × 31, and the numbers that divide it are [1, 5, 25, 31, 155, 775].½ mark
4. Work done. The algorithm makes one divisibility check for each j from 1 to n: 15 checks, 135 checks and 775 checks. So the work is proportional to the size of the number, not to how many divisors it has (775 has fewer divisors than 135 but needs almost 6 times as many checks).1 mark
5. Each extra digit makes a number about 10 times larger, so it makes the work about 10 times larger: a 3-digit number needs hundreds of checks, a 5-digit number tens of thousands.½ mark

Check: Pairs multiply back to the number: 135 = 1 × 135 = 3 × 45 = 5 × 27 = 9 × 15; 775 = 1 × 775 = 5 × 155 = 25 × 31 ✓.

Answer to write in the exam

Common mistakes that cost marks

• Missing 27 and 45 as divisors of 135, or 31 and 155 as divisors of 775 (a prime factor like 31 is easy to overlook).
• Saying the work depends on how many divisors there are. The algorithm checks every number up to n, so it depends on n.
• Saying the work grows with the number of digits (adding 1 more step per digit). Here each extra digit multiplies the work by about 10.

How this can come in the exam

Try one yourself

Find the divisors of 196 by the algorithm. How many checks are made?

More questions like this

• If we look through the divisors of 375 and 825 above, we see that the answer is 75. What if the numbers were 54000 and 81000?
• Suppose we want to compute gcd(375, 825).
• Suppose List 1 and List 2 are two lists of numbers in increasing order.
• Describe an algorithm to compute the least common multiple (lcm) of two numbers.
• Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).

All Algorithms questions · All maths questions