GCD, LCM & Extended Euclidean Algorithm Code Implementations
Complete GCD, LCM & Extended Euclidean Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read GCD, LCM & Extended Euclidean Algorithm Guide ยท Launch Interactive Visualizer
C++ Implementation
// GCD and LCM Implementation in C++
#include <iostream>
#include <cstdlib>
class GcdLcm {
public:
// Euclidean algorithm for GCD
static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return std::abs(a);
}
// LCM using GCD
static int lcm(int a, int b) {
return std::abs(a * b) / gcd(a, b);
}
};CPP Implementation
Time: O(log(n)) | Space: O(1)
gcd
#include <iostream>
#include <algorithm>
using namespace std;
class GCDLCM {
public:
// Euclidean Algorithm for GCD
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// Recursive version
int gcdRecursive(int a, int b) {
if (b == 0) return a;
return gcdRecursive(b, a % b);
}
// LCM using GCD
int lcm(int a, int b) {
return (a / gcd(a, b)) * b;
}
// Extended Euclidean Algorithm
pair<int, pair<int, int>> extendedGcd(int a, int b) {
if (b == 0) {
return {a, {1, 0}};
}
auto result = extendedGcd(b, a % b);
int gcd = result.first;
int x = result.second.second;
int y = result.second.first - (a / b) * result.second.second;
return {gcd, {x, y}};
}
// GCD of multiple numbers
int gcdMultiple(const vector<int>& numbers) {
int result = numbers[0];
for (int i = 1; i < numbers.size(); i++) {
result = gcd(result, numbers[i]);
}
return result;
}
// LCM of multiple numbers
int lcmMultiple(const vector<int>& numbers) {
int result = numbers[0];
for (int i = 1; i < numbers.size(); i++) {
result = lcm(result, numbers[i]);
}
return result;
}
};JAVA Implementation
// GCD and LCM Implementation in Java
public class GcdLcm {
// Euclidean algorithm for GCD
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return Math.abs(a);
}
// LCM using GCD
public static int lcm(int a, int b) {
return Math.abs(a * b) / gcd(a, b);
}
}JAVASCRIPT Implementation
// GCD and LCM Implementation in JavaScript
// Euclidean algorithm for GCD
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return Math.abs(a);
}
// LCM using GCD
function lcm(a, b) {
return Math.abs(a * b) / gcd(a, b);
}PYTHON Implementation
# GCD and LCM Implementation in Python
# Euclidean algorithm for GCD
def gcd(a, b):
while b:
a, b = b, a % b
return abs(a)
# LCM using GCD
def lcm(a, b):
return abs(a * b) // gcd(a, b)