Smallest Common Multiple Solution

Question

Find the smallest common multiple of the provided parameters that can be evenly divided by both, as well as by all sequential numbers in the range between these parameters.

The range will be an array of two numbers that will not necessarily be in numerical order.

For example, if given 1 and 3, find the smallest common multiple of both 1 and 3 that is also evenly divisible by all numbers between 1 and 3. The answer here would be 6.

Explanation of the Question

1. Smallest common multiple is the same thing as the Lowest Common Multiple (LCM).

2. That can be evenly divided means to divide with no remainder.

3. An array would be the input but it may not be in numerical order so you have to find the max and min of the range for proper formatting.

Solution

The LCM of two numbers is the same as the product of those two numbers divided by their Greatest Common Divisor - GCD.

Luckily for us, LCM operation is associative i.e

LCM (a, b, c) = LCM ( LCM (a, b) , c) or vice versa and you can spread it.

So, we just have to keep iterating through the array to figure the final LCM.

It is normal to think how would that work, but it does all thanks to our GCD that gives us a very small number.

Final Code

# Little setback is that how input would be given
# Gets input separate by spaces
arr = [int(x) for x in input().split()]

# this part gets the min and max incase 
# not properly formatted from line 3
max = max(arr)
min = min(arr)

# Populating the array
between = [i for i in range(min, max+1)]

# Finds the LCM
def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 

    # This part handles the GCD
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den

    # This is the formula for getting the LCM from GCD
    lcm = int(int(num1 * num2)/int(gcd)) 
    return lcm 

# For the first sets
num1 = between[0] 
num2 = between[1] 
lcm = find_lcm(num1, num2) 

# Iterates through the whole array and compares
# This part works because it uses the GCD and no matter what
for i in range(2, len(between)): 
    lcm = find_lcm(lcm, between[i]) 

print(lcm)