GCD and LCM Euclidean Algorithm in DSA Python - Build from Scratch

GCD and LCM using Euclidean Algorithm

📖 Scenario: Imagine you are helping a friend who wants to find the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. These are useful in many real-life situations like sharing items equally or finding common schedules.

🎯 Goal: You will write a small program that calculates the GCD and LCM of two given numbers using the Euclidean algorithm.

📋 What You'll Learn

Create two integer variables with exact values

Use a variable to hold the original values for calculation

Implement the Euclidean algorithm to find the GCD

Calculate the LCM using the GCD

Print the GCD and LCM in the specified format

💡 Why This Matters

🌍 Real World

Finding GCD and LCM helps in tasks like dividing items equally, scheduling events, and simplifying fractions.

💼 Career

Understanding these algorithms is useful for software developers working on math-related applications, data analysis, and optimization problems.

1

Create two integer variables

Create two integer variables called num1 and num2 with values 48 and 180 respectively.

DSA Python

# Your code here

Hint

Use simple assignment to create num1 and num2.

2

Create copies of the numbers for calculation

Create two new variables called a and b and set them equal to num1 and num2 respectively.

DSA Python

num1 = 48
num2 = 180
# Your code here

Hint

Assign a and b to keep original numbers safe.

3

Calculate the GCD using Euclidean algorithm

Use a while loop with condition b != 0. Inside the loop, create a temporary variable temp to store b, then update b to a % b, and finally update a to temp. This will calculate the GCD and store it in a.

DSA Python

num1 = 48
num2 = 180
a = num1
b = num2
# Your code here

Hint

The Euclidean algorithm repeatedly replaces the larger number by the remainder until the remainder is zero.

4

Calculate and print the GCD and LCM

Create a variable called gcd and set it equal to a. Then calculate the LCM using the formula (num1 * num2) // gcd and store it in a variable called lcm. Finally, print the GCD and LCM in the format: "GCD: <gcd>" and "LCM: <lcm>".

DSA Python

num1 = 48
num2 = 180
a = num1
b = num2
while b != 0:
    temp = b
    b = a % b
    a = temp
# Your code here

Hint

Use integer division // to calculate LCM and print results exactly as shown.