최대공약수 (GCD, Greatest Common Divisor)
- 유클리드 호제법
Python 코드
1
2
3
4
5
6
7
8
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
a, b = b, a % b
return a
Java 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int gcd(int a, int b) {
if (a < b) {
int temp = a;
a = b;
b = temp;
}
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
최소공배수 (LCM, Least Common Multiple)
- 두 수의 곱을 최대공약수로 나눈다.
Python 코드
1
2
def lcm(a, b):
return a * b // gcd(a, b)
Java 코드
1
2
3
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}