AQA GCSE Computer Science sample Paper 1, Question 17: the highest common factor bug
AQA 8525 sample assessment material, Paper 1 Question 17: a Python program finds the highest common factor of two numbers but gives 2 for 4 and 4. The output, the line with the error, and the fix. With the program to run on both pairs.
Question 17 of AQA's sample assessment material for GCSE Computer Science Paper 1 (8525/1B, the Python paper) is three one mark parts about a program with an off-by-one error. It is the pattern of every "the program works sometimes" question since.
We do not copy the paper here. Open it beside this page: AQA 8525 Paper 1B sample question paper (PDF). When you have finished, check the sample mark scheme too.
The question in short
The program reads two numbers, sets hcf to 1 and count to 1, and loops while count is less than num1: if both numbers divide exactly by count, hcf becomes count. Then count goes up by 1. Finally it prints hcf.
For 4 and 6 it correctly prints 2. For 4 and 4 it should print 4, and does not.
The three parts
17.1 The output for 4 and 4. The loop tries count = 1, 2 and 3, and stops before 4. Both divide by 1 and by 2, so hcf ends at 2.
17.2 The line with the error. Line 5, the while condition.
17.3 The fix. Change < to <=, so that count reaches num1. (Or change num1 to num1 + 1.)
Why it worked for 4 and 6
The answer, 2, is smaller than 4, so the loop reached it before stopping. The bug only shows when the highest common factor is num1 itself, which happens when num1 divides num2 exactly. Boundary test data finds this kind of thing.
Where the marks are lost
- 4 for part 17.1. The question says it does not output 4. Trace the loop as written.
- Line 6 or line 7. The condition on line 6 and the assignment on line 7 are fine. The loop never lets them see
count= 4. - "Add 1 somewhere". Say which line and what it becomes.
Run it
The program, with FIXED to switch between the paper's condition and the corrected one. It prints every factor it tries.
The program
from bugbot import *
connect()
# False is the program on the paper
FIXED = False
num1 = int(input("First number: "))
num2 = int(input("Second number: "))
hcf = 1
count = 1
if FIXED:
last = num1 # count <= num1
else:
last = num1 - 1 # count < num1, as on the paper
while count <= last:
if num1 % count == 0 and num2 % count == 0:
hcf = count
print("both divide by", count)
count = count + 1
print(hcf)
forward(60, distance=hcf * 5)
Questions
What are the answers to AQA sample Paper 1 Question 17?
17.1: 2. 17.2: line 5. 17.3: change the < to <=, so the loop also tests count equal to num1.
What is the highest common factor?
The largest number that divides both numbers with no remainder. For 6 and 9 it is 3; for 2 and 5 it is 1.
What is an off-by-one error?
A loop that runs one time too few or too many, usually from mixing up < and <=. Test with data where the answer is at the very edge of the range to catch it.
More from this paper
Every AQA 8525 question we have worked
Learn it step by step
- F6.4 Debugging logic errors Robust programs
- F2.6 Condition-controlled loops: while Decisions and loops
This is our own explanation of a published exam question. It is not written or endorsed by AQA, and the question paper and mark scheme remain AQA's copyright. Read them on AQA's site with the links on this page.