Compute GCD and LCM of Two Integers

AIM

To write a Python program that computes the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two integers.

ALGORITHM

1. Start
2. Input two integers num1 and num2
3. Initialize gcd = 1
4. Check if num1 is divisible by num2
5. If yes, then gcd = num2
6. Otherwise, iterate from num2//2 down to 2
7. Find the largest number that divides both num1 and num2
8. Calculate LCM using formula: LCM = (num1 × num2) / GCD
9. Display the GCD and LCM
10. Stop

PROGRAM

# Compute the greatest common divisor and least common multiple of two integers.

num1 = int(input("Enter First Number:"))
num2 = int(input("Enter Second Number:"))

gcd = 1

if num1 % num2 == 0:
    gcd = num2
else:
    for k in range(num2//2, 1, -1):
        if num1 % k == 0 and num2 % k == 0:
            gcd = k
            break

lcm = (num1 * num2) / gcd

print("GCD is:", gcd)
print("LCM is:", lcm)

OUTPUT

CONCLUSION

Thus, the given program was successfully executed and the output was verified as per the expected result.

VIVA QUESTIONS

1. What is the difference between GCD and LCM?

   GCD is the largest number that divides both numbers, while LCM is the smallest number that both numbers can divide. They are inversely related through the formula: GCD × LCM = num1 × num2.

2. Why do we start the loop from num2//2?

   The largest possible common divisor (other than the number itself) cannot be greater than half of the smaller number. This optimization reduces the number of iterations.

3. What happens if we input two prime numbers?

   If both numbers are prime and different, their GCD will be 1 (they are coprime) and their LCM will be their product.

4. Can you explain the Euclidean algorithm for GCD?

   The Euclidean algorithm uses repeated division: GCD(a,b) = GCD(b, a%b) until the remainder becomes 0. It's more efficient than our current approach.

5. What is the time complexity of this algorithm?

   The time complexity is O(min(num1, num2)) in the worst case, as we might iterate through half of the smaller number.

6. Why is LCM calculated as (num1 * num2) / gcd?

   This formula comes from the mathematical relationship that for any two numbers, their product equals the product of their GCD and LCM.

7. What would happen if one of the inputs is 0?

   If one number is 0, the GCD would be the other number (by convention), but LCM would be undefined or 0. The program should include input validation.

8. How can we modify this program to handle negative numbers?

   We can use the absolute values of the inputs since GCD and LCM are typically defined for positive integers: abs(num1) and abs(num2).