2. Lowest common multiple

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

2.1. LCM

The lowest common multiple, LCM, of two or more numbers is the smallest positive integer that is divisible by each of the numbers.
For example, the LCM of 4 and 6 is 12, because 12 is the smallest positive integer that is divisible by both 4 and 6.

2.2. LCM pseudocode

The Pseudocode to find LCM of two numbers has the steps to find the lowest common multiple of two numbers:
begin
// Declare variables for the two numbers and the LCM
number num1, num2, lcm
list factors1, factors2, all_factors

// Prompt the user to enter the two numbers
ouput “Enter the first number: “
input num1
ouput “Enter the second number: “
input num2

// Find the prime factors of each number
factors1 ← prime_factors(num1)
factors2 ← prime_factors(num2)

// Find the union of all the prime factors with highest power
all_factors ← union(factors1, factors2)

// Multiply all the prime factors
lcm ← product(all_factors)

// Display the LCM
ouput “The LCM of “ + num1 + “ and “ + num2 + “ is “ + lcm
end
  1import math
  2
  3
  4def frequency(lst):
  5    """Return a dictionary with the frequency of each factor in lst.
  6
  7    Args:
  8        lst (list): A list of integers.
  9
 10    Returns:
 11        dict: A dictionary with factors as keys and frequencies as values.
 12    """
 13    # Create an empty dictionary to store the frequency
 14    freq = {}
 15    # Loop through the list
 16    for x in lst:
 17        # If x is already in the dictionary, increment its value by 1
 18        if x in freq:
 19            freq[x] += 1
 20        # Otherwise, set its value to 1
 21        else:
 22            freq[x] = 1
 23    # Return the dictionary
 24    return freq
 25
 26
 27def union_of_highest_powers(lst1, lst2):
 28    """Return a list with the union of factors with highest power from lst1 and lst2.
 29
 30    Args:
 31        lst1 (list): A list of integers.
 32        lst2 (list): A list of integers.
 33
 34    Returns:
 35        list: A list of integers with factors raised to highest power.
 36    """
 37    # Create an empty list to store the result
 38    result = []
 39    # Count how many times each factor appears in each list
 40    freq1 = frequency(lst1)
 41    freq2 = frequency(lst2)
 42    # Loop through the keys of freq1 (the factors in lst1)
 43    for x in freq1:
 44        # If x is also in freq2 (the factors in lst2), compare their values (the powers)
 45        if x in freq2:
 46            # If freq1[x] is greater than or equal to freq2[x], append x raised to freq1[x] to the result list
 47            if freq1[x] >= freq2[x]:
 48                result.append(x ** freq1[x])
 49            # Otherwise, append x raised to freq2[x] to the result list
 50            else:
 51                result.append(x ** freq2[x])
 52        # Otherwise, append x raised to freq1[x] to the result list
 53        else:
 54            result.append(x ** freq1[x])
 55    # Loop through the keys of freq2 (the factors in lst2)
 56    for y in freq2:
 57        # If y is not in freq1 (the factors in lst1), append y raised to freq2[y] to the result list
 58        if y not in freq1:
 59            result.append(y ** freq2[y])
 60    # Return the result list
 61    return result
 62
 63
 64def product(lst):
 65    """Return the product of all elements in lst.
 66
 67    Args:
 68        lst (list): A list of numbers.
 69
 70    Returns:
 71        number: The product of all elements in lst.
 72    """
 73    # Initialize the product to 1
 74    p = 1
 75    # Loop through the list and multiply each element with the product
 76    for x in lst:
 77        p *= x
 78    # Return the product
 79    return p
 80
 81
 82def get_prime_factors(num):
 83    """Return a list with the prime factors of num.
 84
 85    Args:
 86        num (int): A positive integer.
 87
 88    Returns:
 89        list: A list of integers with prime factors of num.
 90
 91    Raises:
 92        ValueError: If num is not positive.
 93    """
 94
 95    if num <= 0:
 96        raise ValueError("num must be positive")
 97
 98    max_possible = int(math.sqrt(num)) + 1
 99    prime_factors = list()
100    while num % 2 == 0:
101        prime_factors.append(2)
102        num = num // 2
103    for factor in range(3, max_possible, 2):
104        while num % factor == 0:
105            prime_factors.append(factor)
106            num = num // factor
107    if num > 2:
108        prime_factors.append(num)
109    return prime_factors
110
111
112# Define a main function to run the script
113def main():
114    """Prompt the user to enter two numbers and display their LCM."""
115
116    # Prompt the user to enter two numbers and convert them to integers
117    num1 = int(input("Enter the first number: "))
118    num2 = int(input("Enter the second number: "))
119
120    # Find the prime factors of each number using the get_prime_factors function
121    factors1 = get_prime_factors(num1)
122    factors2 = get_prime_factors(num2)
123
124    # Find the union of all the prime factors with highest power using the union_of_highest_powers function
125    all_factors = union_of_highest_powers(factors1, factors2)
126
127    # Find the LCM by multiplying all the factors using the product function
128    lcm = product(all_factors)
129
130    # Display the LCM
131    print(f"prime factors of {num1} is{factors1}.")
132    print(f"prime factors of {num2} is{factors2}.")
133    print(f"LCM({num1}, {num2}) is {lcm}; the product of {all_factors}.")
134
135
136# Check if the script is run directly and call the main function
137if __name__ == "__main__":
138    main()
139
140'''
141Enter the first number: 12
142Enter the second number: 18
143prime factors of 12 is[2, 2, 3].
144prime factors of 18 is[2, 3, 3].
145LCM(12, 18) is 36; the product of [4, 9]. 
146'''

2.3. LCM of multiple numbers

The lowest common multiple of triples or more natural numbers can be found by finding multiplying the highest power of their prime factors.
  1import math
  2
  3
  4def frequency(lst):
  5    """Return a dictionary with the frequency of each factor in lst.
  6
  7    Args:
  8        lst (list): A list of integers.
  9
 10    Returns:
 11        dict: A dictionary with factors as keys and frequencies as values.
 12    """
 13    # Create an empty dictionary to store the frequency
 14    freq = {}
 15    # Loop through the list
 16    for x in lst:
 17        # If x is already in the dictionary, increment its value by 1
 18        if x in freq:
 19            freq[x] += 1
 20        # Otherwise, set its value to 1
 21        else:
 22            freq[x] = 1
 23    # Return the dictionary
 24    return freq
 25
 26
 27def union_of_highest_powers(nums):
 28    """Return a list with the union of all factors with highest power.
 29
 30    Args:
 31        nums (list): A list of positive integers.
 32
 33    Returns:
 34        list: A list of integers with factors raised to their highest power.
 35
 36    Raises:
 37        ValueError: If any element in nums is not positive.
 38    """
 39    # Create an empty list to store the result
 40    result = []
 41    # If there are no numbers or only one number, return 1
 42    if len(nums) == 0 or len(nums) == 1:
 43        return [1]
 44    # Create an empty dictionary to store the frequency of each factor in all numbers
 45    freq2 = {}
 46    # Loop through each number in nums
 47    for num in nums:
 48        # Find the prime factors of num using a get_prime_factors algorithm
 49        prime_factors = get_prime_factors(num)
 50        # Find the frequency of each factor in num using the frequency function
 51        freq1 = frequency(prime_factors)
 52        # Loop through each factor in freq1
 53        for x in freq1:
 54            # If x is also in freq2, compare their values (the powers)
 55            if x in freq2:
 56                # If freq1[x] is greater than freq2[x], update freq2[x] to freq1[x]
 57                if freq1[x] > freq2[x]:
 58                    freq2[x] = freq1[x]
 59            # Otherwise, add x and freq1[x] to freq2
 60            else:
 61                freq2[x] = freq1[x]
 62    # Loop through each factor in freq2
 63    for y in freq2:
 64        # Append y raised to freq2[y] to the result list
 65        result.append(y ** freq2[y])
 66    # Return the result list
 67    return result
 68
 69
 70def product(lst):
 71    """Return the product of all elements in lst.
 72
 73    Args:
 74        lst (list): A list of numbers.
 75
 76    Returns:
 77        number: The product of all elements in lst.
 78    """
 79    # Initialize the product to 1
 80    p = 1
 81    # Loop through the list and multiply each element with the product
 82    for x in lst:
 83        p *= x
 84    # Return the product
 85    return p
 86
 87
 88def get_prime_factors(num):
 89    """Return a list with the prime factors of num.
 90
 91    Args:
 92        num (int): A positive integer.
 93
 94    Returns:
 95        list: A list of integers with prime factors of num.
 96
 97    Raises:
 98        ValueError: If num is not positive.
 99    """
100    if num <= 0:
101        raise ValueError("num must be positive")
102
103    max_possible = int(math.sqrt(num)) + 1
104    prime_factors = list()
105    while num % 2 == 0:
106        prime_factors.append(2)
107        num = num // 2
108    for factor in range(3, max_possible, 2):
109        while num % factor == 0:
110            prime_factors.append(factor)
111            num = num // factor
112    if num > 2:
113        prime_factors.append(num)
114    return prime_factors
115
116
117# Define a main function to run the script
118def main():
119    """Prompt the user to enter a list of integers and display their LCM."""
120    # Prompt the user to enter a list of integers and convert them to lists
121    nums = input("Enter the numbers separated by commas: ")
122    nums = [int(num) for num in nums.split(",")]
123    # Find the union of all the factors with highest power using the union_of_highest_powers function
124    all_factors = union_of_highest_powers(nums)
125    # Find the LCM by multiplying all the factors using the product function
126    lcm = product(all_factors)
127    # Display the LCM
128    print(f"LCM({nums}) is {lcm}; the product of {all_factors}.")
129
130
131# Check if the script is run directly and call the main function
132if __name__ == "__main__":
133    main()
134
135
136'''
137Enter the numbers separated by commas: 12,15,16
138LCM([12, 15, 16]) is 240; the product of [16, 3, 5].
139'''

2.4. LCM using gcd

The Python math.gcd() function is a built-in function that returns the greatest common divisor (GCD) of two or more integers.
The GCD of two or more numbers is the largest positive integer that divides each of the numbers without leaving a remainder.
Use the formula lcm = (a * b) // gcd(a, b)
 1# Import the math module to use the gcd function
 2import math
 3
 4# Define a function to find the lcm of two numbers
 5def lcm(a, b):
 6    # Use the formula lcm = (a * b) // gcd(a, b)
 7    return (a * b) // math.gcd(a, b)
 8
 9# Prompt the user to enter two numbers
10num1 = int(input("Enter the first number: "))
11num2 = int(input("Enter the second number: "))
12
13# Call the lcm function and print the result
14print("The LCM of", num1, "and", num2, "is", lcm(num1, num2))
15
16
17a = 48
18b = 18
19# Display the LCM
20print(f'LCM({a}, {b}) is {lcm(a , b)}.')
21

2.5. LCM of multiple numbers using gcd

The code belwo handles multiple positive integers.
 1# Import the math module to use the gcd function
 2import math
 3
 4# Define a function to find the lcm of any number of numbers
 5def lcm(*args):
 6    # Use the formula lcm(a, b, c) = lcm(lcm(a, b), c)
 7    result = args[0]
 8    for num in args[1:]:
 9        result = (result * num) // math.gcd(result, num)
10    return result
11
12# Prompt the user to enter any number of numbers separated by commas
13nums = input("Enter the numbers separated by spaces: ")
14nums = [int(num) for num in nums.split(",")]
15
16# Display the LCM
17print(f'The LCM of {", ".join(str(num) for num in nums)} is {lcm(*nums)}.')
18
19'''Enter the numbers separated by spaces: 12 15 16
20The LCM of 12, 15, 16 is 240.'''
21