약수
1과 자기 자신을 제외한 자연수로 나누었을 때 나머지가 0이 되는 수
ex)
12의 약수 : 2, 3, 4, 6
9의 약수 : 3
공약수
공통되는 약수
ex)
6과 8의 공약수 : 2
10과 20의 공약수 : 2, 5, 10
18, 24, 36의 공약수 : 2, 3, 6
최대공약수 (Greatest Common Divisor)
공약수 중에서 가장 큰 수
ex)
6과 8의 최대공약수 : 2
10과 20의 최대공약수 : 10
18, 24, 36의 최대공약수 : 6
배수
자기 자신에 자연수를 곱해서 나오는 수
ex)
2의 배수 : 2, 4, 6, \(\cdots\)
12의 배수 : 12, 24, 36, \(\cdots\)
공배수
공통되는 배수
6과 8의 공배수 : 24, 48, 72, \(\cdots\)
10과 20의 공배수 : 20, 40, 60, \(\cdots\)
18, 24, 36의 공배수 : 72, 144, 216, \(\cdots\)
최소공배수 (Least Common Multiple)
공배수 중에서 가장 작은 수
ex)
6과 8의 최소공배수 : 24
10과 20의 최소공배수 : 20
18, 24, 36의 최소공배수 : 72
최대공약수와 최소공배수 계산하기
최대공약수는 소인수분해의 개념을 이해하면 된다.
12 = 2^2 * 3^1
18 = 2^1 * 3^2
최대공약수는 공통되는 부분인 2^1 * 3^1 = 6이다.
이 때, 최소공배수는 모두를 포함하는 개념으로
2^2 * 3^2 = 36이 된다.
따라서 다음 관계가 성립한다.
두 수 a, b 에 대하여
a, b의 최소공배수 = a * b / a, b의 최대공약수
ex)
12, 18
최대공약수 : 6
최소공배수 : 12 * 18 / 6 = 36
18, 24, 36
18과 24의 최대공약수 : 6
18과 24의 최대공배수 : 18 * 24 / 6 = 72
72와 36의 최대공약수 : 36
72와 36의 최소공배수 : 72 * 36 / 36 = 72
Python 구현
method 1 : 두 수중 작은 수 a부터 1까지 공약수가 되는지 체크한다.
a, b = sorted(map(int, input().split()))
for i in range(a, 0, -1):
if (a % i == 0) and (b % i == 0):
break
print(i)
print(int(a * b / i))
12 18
>>> 6
36장점 : 구현이 간단
단점 : 숫자가 커질 경우 시간에 대한 가성비가 나쁘다.
method 2 : 유클리드 호제법
서로 나누었을 때의 나머지가 다른 작은 수 와 나누어 떨어지면 그 나머지가 최대공약수이다.
a, b = sorted(map(int, input().split()))
x, y = a, b
while y:
x, y = y, x % y
print(x, y)
print(x)
print(int(a * b / x))
12 18
>>> 18 12
12 6
6 0
6
36장점 : 숫자가 커져도 계산횟수가 크게 늘어나지 않는다. 따라서 빠르다.
단점 : 생각을 하거나 알고리즘을 외워둬야한다.
method 3 : math 라이브러리 활용
a, b = map(int, input().split())
print(math.gcd(a, b))
print(math.lcm(a, b))
12 18
>>> 6
36장점 : 유클리드 호제법을 직접 구현하지 않아도 간편하게 사용가능
단점 : 일부 코딩테스트에서 math라이브러리를 제한하는 경우 사용불가능
댓글