파이썬 최대공약수와 최소공배수(BOJ 2609)
2022, Jul 26
유클리드 호제법에 대하여
문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
예제 입력 1
24 18
예제 출력 1
6
72
📝 풀어보기
📌 푸는데에 여러가지 방법이 있겠지만 그 중에 유클리드 호제법을 사용해서 풀어봤다.
유클리드 호제법은 x, y의 최대공약수는 y, x%y(x를 y로 나눈 나머지 값)과 같다는 공식인데 예시를 들어서 보자.
x = 10, y = 12 일때,
10 % 12 = 10
12 % 10 = 2
10 % 2 = 0
최소공배수 2
몫을 나눈 나머지가 0이 되었을때 2가 10과 12의 최소 공배수가 된다.
위의 예제도 해보자.
x = 24, y = 18 일때,
24 % 18 = 6
18 % 6 = 0
최소공배수 6
📌 유클리드 호제법을 이용해서 함수를 만든다.
A, B = map(int, input().split())
def GCD(x, y):
while y: # y가 0이 될때까지 실행
x, y = y, x%y
📌 함수 내에서 최소공배수도 계산하여 반환한다. 최소공배수는 A와 B의 곱에 최소공배수를 나누면 얻을수 있다.
min = A*B/x
print(x)
print(min)
GCD(A, B)
전체코드
A, B = map(int, input().split())
def GCD(x,y):
while y:
x, y = y, x%y
min = A*B/x
print(x)
print(int(min))
GCD(A, B)