1. Highest common factors
VC2M5N10: level 6: Follow a mathematical algorithm involving branching and repetition (iteration); create and use algorithms involving a sequence of steps and decisions and digital tools to experiment with factors, multiples and divisibility; identify, interpret and describe emerging patterns
identifying lowest common multiples and highest common factors of pairs or triples of natural numbers; for example, the lowest common multiple of {6, 9} is 18, and the highest common factor is 3, and the lowest common multiple of {3, 4, 5} is 60 and the highest common factor is 1
1.1. Euclidean algorithm for HCF
See: https://en.wikipedia.org/wiki/Euclidean_algorithm
The highest common factor, HCF, is known as the greatest common divisor, gcd.
The Euclidean algorithm is based on the principle that the highest common factor of two numbers does not change if the larger number is replaced by its difference with the smaller number.
For example, 6 is the HCF of 48 and 18 (as 48 = 8 x 6 and 18 = 3 x 6), and the same number 6 is also the HCF of 18 and 30 (obtained by 48 - 18; taking 3 sixes from 8 sixes leaves 5 sixes).
Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal.
48 and 18 becomes 30 and 18 which becomes 18 and 12 which becomes 12 and 6 which becomes 6 and 6.
When that occurs, they are the HCF of the original two numbers.
1.2. HCF pseudocode
The pseudocode to find HCF of two numbers by repeated subtraction is below.
function hcf_sub(a, b)
// Repeat until the two numbers are equal
while a is not equal to b
// If a is larger than b, subtract b from a
if a is greater than b
a ← a minus b
// Otherwise, subtract a from b
else
b ← b minus a
// Return either a or b as the HCF
return a
1.3. HCF by repeated subtraction
1def hcf_sub(a, b):
2 while a != b:
3 if a > b:
4 a = a - b
5 else:
6 b = b - a
7 return a
8
9
10a = 48
11b = 18
12
13print(f'HCF({a}, {b}) is {hcf_sub(a, b)}.')
14# HCF(48, 18) is 6.
1.4. HCF by repeatedly getting remainders from division
Instead of repeated subtractions, a division can be used to get the remainder that would occur if all the possible subtractions of that number were to be done at once.
Starting with 48 and 18, instead of subtracting 18 from 48, subtract the largest multiple of 18 that is less than 48.
48 - (48//18)*18 = 12
48 - 2*18 = 12.
Note that 48//18 gives 2, the largest multiple of 18 that is less than 48.
// is floor division, rounding down to an integer.
The code below runs the while loop until b equals 0.
b is stored in t so b can be calculated, then a is set to t.
An example of b = a - (a // b) * b
is b = 48 - (48//18)*18,
which is b = 48 - 36 = 12.
1def hcf_div(a, b):
2 while b != 0:
3 t = b
4 b = a - (a // b) * b
5 a = t
6 return a
7
8
9a = 48
10b = 18
11print(f'HCF({a}, {b}) is {hcf_div(a, b)}.')
12# HCF(48, 18) is 6.
The line, b = a - (a // b) * b, can be replaced by b = a % b, which finds the remainder from division.
Instead of: 48 - (48//18)*18 = 12
use: 48 % 18 = 12
1def hcf_mod(a, b):
2 while b != 0:
3 t = b
4 b = a % b
5 a = t
6 return a
7
8
9a = 48 #1071
10b = 18 #462
11
12print(f'HCF({a}, {b}) is {hcf_mod(a, b)}.')
13# HCF(48, 18) is 6.
1.5. HCF of triples and more
The highest common factors of triples or more natural numbers can be found by finding the HCF of two numbers first, then finding the HCF of the result and a third number and so on for all numbers being tested.
e.g. HCF(168, 180, 192) is 12.
1.6. HCF of triples and more by repeated subtraction
The code below uses repeated subtraction with multiple numbers to find their HCF.
1# Define a function to find the hcf of any number of numbers using subtraction
2def hcf_sub_multi(*args):
3 # Use the logic for subtraction a-b-c-... = ((a-b)-c)-...
4 result = args[0]
5 for num in args[1:]:
6 while result != num:
7 if result > num:
8 result = result - num
9 else:
10 num = num - result
11 return result
12
13# Prompt the user to enter any number of numbers separated by commas; 168, 180, 192
14nums = input("Enter the numbers: ")
15nums = [int(num) for num in nums.split(",")]
16
17# Call the hcf_sub function and print the result
18print(f'The HCF of {", ".join(str(num) for num in nums)} is {hcf_sub_multi(*nums)}.')
19# The HCF of 168, 180, 192 is 12.
20
1.7. HCF of triples and more by math.gcd
The code below uses the python math.gcd function for multiple numbers to find their HCF.
The code uses error chekcing as well.
1import math
2
3
4def hcf_gcd(*args):
5 """Find the highest common factor (HCF) or greatest common divisor (GCD) of any number of numbers using math.gcd.
6
7 Args:
8 *args: Any number of integer arguments.
9
10 Returns:
11 int: The HCF or GCD of the given numbers.
12
13 Raises:
14 TypeError: If any of the arguments are not integers.
15 """
16 # Try to find the hcf using math.gcd
17 try:
18 result = args[0]
19 for num in args[1:]:
20 result = math.gcd(result, num)
21 return result
22 # Handle the TypeError if it occurs
23 except TypeError:
24 print("All arguments must be positive integers")
25 return 0
26
27
28def main():
29 # Prompt the user to enter any number of positive integers separated by commas; 168, 180, 192
30 nums = input("Enter the positive integers: ")
31
32 # Check if the user enters any numbers at all
33 if nums == "":
34 print("Please enter at least one positive integers")
35 else:
36 # Try to convert the input to a list of integers
37 try:
38 nums = [int(num) for num in nums.split(",")]
39
40 # Check if any of the numbers are negative
41 if any(num < 0 for num in nums):
42 print("The HCF is only defined for positive integers")
43 else:
44 # Call the hcf_gcd function and print the result
45 print(f'The HCF of {", ".join(str(num) for num in nums)} is {hcf_gcd(*nums)}.')
46 # The HCF of 168, 180, 192 is 12.
47 # Handle the ValueError if it occurs
48 except ValueError:
49 print("Please enter only positive integers")
50
51if __name__ == "__main__":
52 main()
53
54
55