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

GCD and LCM using Euclidean Algorithm

📖 Scenario: 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 scheduling events.

🎯 Goal: Build a simple C program that calculates the GCD and LCM of two given numbers using the Euclidean Algorithm.

📋 What You'll Learn

Create two integer variables a and b with exact values 48 and 18

Create an integer variable original_a to store the original value of a

Use a while loop with condition b != 0 to find the GCD using the Euclidean Algorithm

Calculate the LCM using the formula (original_a * 18) / a

Print the GCD and LCM with the exact format shown

💡 Why This Matters

🌍 Real World

Finding GCD and LCM helps in tasks like dividing items into equal groups or finding common schedules.

💼 Career

Understanding algorithms like Euclidean Algorithm is fundamental for programming jobs that involve problem solving and optimization.

1

Create the initial numbers

Create two integer variables called a and b and set them to 48 and 18 respectively.

DSA C

# Your code here

Hint

Use int a = 48; and int b = 18; to create the variables.

2

Save original value of a

Create an integer variable called original_a and set it equal to a to keep the original value for later.

DSA C

int a = 48;
int b = 18;
# Your code here

Hint

Use int original_a = a; to save the original value.

3

Calculate the GCD using Euclidean Algorithm

Use a while loop with the condition b != 0. Inside the loop, create an integer 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 C

int a = 48;
int b = 18;
int original_a = a;
# Your code here

Hint

Use the Euclidean Algorithm steps inside the while loop to find the GCD.

4

Calculate and print the GCD and LCM

Create an integer variable lcm and calculate it using the formula (original_a * 18) / a. Then print the GCD and LCM using printf with the exact format:
"GCD: %d\nLCM: %d\n", passing a and lcm respectively.

DSA C

int a = 48;
int b = 18;
int original_a = a;
while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
}
# Your code here

Hint

Calculate LCM using the formula and print both values exactly as shown.