Start with two numbers, repeatedly replace a by b and b by a mod b until b is zero. The last non-zero a is the GCD. Then compute LCM using the formula.
Execution Sample
DSA C
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int lcm(int a, int b) {
return (a / gcd(a, b)) * b;
}
This code finds the GCD of two numbers using the Euclidean algorithm and then calculates the LCM using the GCD.
Execution Table
Step
Operation
a
b
a % b
Pointer Changes
Visual State
1
Start with a=48, b=18
48
18
N/A
a=48, b=18
a=48, b=18
2
Calculate a % b
48
18
12
temp=b=18; b=48%18=12; a=temp=18
a=18, b=12
3
Calculate a % b
18
12
6
temp=b=12; b=18%12=6; a=temp=12
a=12, b=6
4
Calculate a % b
12
6
0
temp=b=6; b=12%6=0; a=temp=6
a=6, b=0
5
b == 0, GCD found
6
0
N/A
Stop loop
GCD=6
6
Calculate LCM
48
18
N/A
LCM = (48 / 6) * 18 = 8 * 18 = 144
LCM=144
💡 Loop stops when b becomes 0; last a is GCD. Then LCM calculated using GCD.
Variable Tracker
Variable
Start
After Step 2
After Step 3
After Step 4
After Step 5
Final
a
48
18
12
6
6
6
b
18
12
6
0
0
0
temp
N/A
18
12
6
N/A
N/A
GCD
N/A
N/A
N/A
N/A
6
6
LCM
N/A
N/A
N/A
N/A
N/A
144
Key Moments - 3 Insights
Why do we replace a with b and b with a % b in each step?
Because the Euclidean algorithm uses the property that GCD(a, b) = GCD(b, a % b). This reduces the problem size each step until b becomes zero, as shown in steps 2-4 in the execution_table.
Why does the loop stop when b becomes zero?
When b is zero, the current value of a is the GCD. This is because no number divides zero except the number itself. This is shown in step 5 where b=0 and GCD=6.
How is LCM calculated using GCD?
LCM is calculated by dividing the product of the original numbers by their GCD: LCM = (a * b) / GCD. This is shown in step 6 where LCM = (48 / 6) * 18 = 144.
Visual Quiz - 3 Questions
Test your understanding
Look at the execution_table, what is the value of 'a' after step 3?
A6
B18
C12
D48
💡 Hint
Check the 'a' column in the execution_table row for step 3.
At which step does the condition 'b != 0' become false?
AStep 5
BStep 4
CStep 6
DStep 3
💡 Hint
Look for the step where b becomes 0 in the execution_table.
If the initial numbers were 30 and 12, how would the final GCD value in variable_tracker change?
AIt would be 18
BIt would be 6
CIt would be 12
DIt would be 30
💡 Hint
Recall that GCD(30,12) is 6, similar to the example's GCD calculation.
Concept Snapshot
GCD (Greatest Common Divisor) finds the largest number dividing two numbers.
Use Euclidean algorithm: repeatedly replace (a, b) with (b, a % b) until b=0.
Last non-zero a is GCD.
LCM (Least Common Multiple) = (a * b) / GCD.
Efficient and fast for large numbers.
Full Transcript
We start with two numbers a and b. We check if b is zero. If not, we calculate a modulo b and update a and b accordingly. We repeat this until b becomes zero. The last non-zero a is the GCD. Then we calculate the LCM by dividing the product of the original numbers by the GCD. This method is called the Euclidean algorithm and is efficient for finding GCD and LCM.
