4. Highest common factors

VC2M5N10: level 5: 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

4.1. Euclidean algorithm

See: https://en.wikipedia.org/wiki/Euclidean_algorithm

The highest common factor 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.

4.2. HCF by repeated subtraction (Euclidean algorithm)

The code below uses a while loop to repeatedly subtract the smaller number from the larger number until both numbers are equal.
The pseudocode for the algorithm is as follows:
FUNCTION HCF_SUB(a, b)
    WHILE a ≠ b
        IF a > b THEN
            a ← a - b
        ELSE
            b ← b - a
        ENDIF
    ENDWHILE
    RETURN a
ENDFUNCTION


BEGIN
    a ← 48
    b ← 18
    result ← HCF_SUB(a, b)
    PRINT "HCF of ", a, " and ", b, " is ", result
END
The python code implementing the algorithm is shown below:
 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.

4.3. 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 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 - 2*18 = 12. Note that 48//18 gives 2. // 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//19)*18, which is b = 48 - 36 = 12.
The pseudocode for the algorithm is as follows:
FUNCTION HCF_DIV(a, b)
    WHILE b ≠ 0
        t ← b
        b ← a - (a // b) * b
        a ← t
    ENDWHILE
    RETURN a
ENDFUNCTION


BEGIN:
    a ← 48
    b ← 18
    result ← HCF_DIV(a, b)
    PRINT "HCF of ", a, " and ", b, " is ", result
END
The python code implementing the algorithm is shown below:
 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 above, b = a - (a // b) * b, can be replaced by b = a % b, which finds the remainder from division.
The pseudocode for the algorithm is as follows:
FUNCTION HCF_MOD(a, b)
    WHILE b ≠ 0
        t ← b
        b ← a % b
        a ← t
    ENDWHILE
    RETURN a
ENDFUNCTION


BEGIN:
    a ← 48
    b ← 18
    result ← HCF_MOD(a, b)
    PRINT "HCF of ", a, " and ", b, " is ", result
END
The python code implementing the algorithm is shown below:
 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.

4.4. 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
 2
 3
 4def hcf_sub_multi(*args):
 5    # Use the logic for subtraction a-b-c-... = ((a-b)-c)-...
 6    result = args[0]
 7    for num in args[1:]:
 8        while result != num:
 9            if result > num:
10                result = result - num
11            else:
12                num = num - result
13    return result
14
15# Prompt the user to enter any number of numbers separated by commas; 168, 180, 192
16nums = input("Enter the numbers: ")
17nums = [int(num) for num in nums.split(",")]
18
19# Call the hcf_sub function and print the result
20print(f'The HCF of {", ".join(str(num) for num in nums)} is {hcf_sub_multi(*nums)}.')
21# The HCF of 168, 180, 192 is 12.
22

FUNCTION HCF_SUB_MULTI(numbers)
    hcf ← FIRST ELEMENT OF numbers

    FOR EACH number IN REMAINING ELEMENTS OF numbers DO
        WHILE hcf ≠ number DO
            IF hcf > number THEN
                hcf ← hcf - number
            ELSE
                number ← number - hcf
            ENDIF
        ENDWHILE
    ENDFOR

    RETURN hcf
ENDFUNCTION

BEGIN
    nums ← USER INPUT "Enter the numbers separated by commas"
    nums ← CONVERT EACH ELEMENT OF SPLIT(nums, ",") TO INTEGER
    result ← HCF_SUB_MULTI(nums)
    PRINT "The HCF of ", nums, " is ", result
END

4.5. 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