📖 문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
예제 입력 1
24 18
예제 출력 1
6
72💻 내 코드
n,m=map(int, input().split())
def gcd(a, b):
while b>0:
a, b=b, a%b
return a
def lcm(a, b):
return int(a*b/gcd(a,b))
print(gcd(n,m))
print(lcm(n,m))
➕ 추가
유클리드 호제법
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
-> b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수
최소공배수: a, b의 곱을 a, b의 최대 공약수로 나눔
파이썬에는 최대공약수와 최소공배수 구하는 내장 함수가 있음
math.gcd(a, b)
math.lcm(a, b)
