최소공배수를 구하는 여러가지 방법에 대해 정리해 보았다. 사실, 최소공배수를 구하는 여러 방법이 아닌 최대공약수를 구하는 여러 방법이 되겠다. 최소공배수는 두 수의 곱에서 최대공약수를 나눈 수이기 때문이다.
1. 최소공약수 직접 구하기
import sys
def gcd(a, b):
if a>b:
a, b = b, a
for i in range(a, 0, -1):
if a%i == 0 and b%i == 0:
break
return i
A, B = map(int, sys.stdin.readline().split())
print(A*B//gcd(A,B))- 우선, 입력받은 수 중 더 큰 수를 a로 만들어준다.
- 그리고 a와 b 모두 나누어 떨어지는 i를 찾는다.
- 여기서 포인트는, for문을 줄이기 위해 가장 큰 a부터 시작해서 하나씩 찾는다는 점이다.
2. math의 gcd 이용
import sys, math
A, B = map(int, sys.stdin.readline().split())
print(A*B//math.gcd(A,B))3. 유클리드 호제법
import sys
def gcd(a, b):
while b>0:
a, b = b, a%b
return a
A, B = map(int, sys.stdin.readline().split())
print(A*B//gcd(A,B))- 문제 의도인 유클리드 호제법으로 푼 코드이다.
- 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 말한다고 한다.
- 그래서 유클리드 호제법은 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한 알고리즘이다.
- 그래서 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대공약수가 된다.
출처: 위키백과
처음에 왜 b가 0이 될 때까지 나머지를 구하는지, r을 r'로 나누는지를 몰랐는데 위키백과의 예시를 보고 이해가 되었다.
예시
1071과 1029의 최대공약수를 구하면,
1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.
- 즉, a와 b의 최대공약수를 구하기 위해 b와 r의 최대공약수를 구하는데, b와 r의 최대공약수를 구하려면 b와 r이 새로운 a와 b가 되어 또다른 b와 r의 최대공약수를 구해야 하는 것이다.
- 이렇게 쭈주죽 b와 r의 최대공약수를 구할 때까지 계속 위 과정이 반복되는 것이다. b와 r의 최대공약수를 구해질 때는 더 이상 b와 r이 a와 b가 되지 않아도 되도록 b가 r로 나누어떨어질 때이다.
- 그래서 계속 b와 r이 a와 b가 되기 때문에 a를 b로 받고, b는 r 즉 a와 b의 나머지로 받는 것이다.
- 이를 b가 r로 나누어떨어질 때 즉, a와 b의 나머지인 b가 0이 될 때까지 반복하면 된다.
결과
문제의도에 맞게 유클리드 호제법으로 푼 결과이다.
