백준 2609_최대공약수와 최소공배수 / Python
2023. 4. 12. 16:00ㆍ백준
문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
## 2609 최대공약수와 최소공배수
n1,n2=map(int,input().split())
sm=min(n1,n2)
bg=max(n1,n2)
for i in range(sm,0,-1): #최소 공배수
if sm%i==0 and bg%i==0:
ans=i
print(i)
break
#최대공약수 * 최소공배수 = 주어지는 두 수의 곱
print((n1*n2)//ans)
최대공약수는 두 수 중에 작은 수를 기준으로 1씩 줄이면서 제일 처음 두 수 모두에게 나누어 떨어지는 수가 최대공약수이다.
최대공배수는 어떻게 구해야할지 감이 안와서 원리를 검색해봤는데 최대공약수*최소공배수=주어지는 두 수의 곱 이라는 엄청난 공식을 알아내서 짱쉽게 풀었다~
'백준' 카테고리의 다른 글
백준 2869_달팽이는 올라가고 싶다 / Python (0) | 2023.04.12 |
---|---|
백준 2775_부녀회장이 될테야~! / Python (0) | 2023.04.12 |
백준 1259_팰린드롬수 / Python (0) | 2023.04.10 |
백준 15829_Hashing / Python (1) | 2023.04.10 |
백준 2798_블랙잭 / Python (0) | 2023.04.10 |