[파이썬] 백준 2609번 최대공약수와 최소공배수 문제 풀이 python

문제 설명

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

문제 링크

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

입출력 예시

프로그램 코드

a, b = map(int, input().split())	#숫자 입력

m = 0	#최대 공약수 저장 숫자

for i in range(1, a + 1):	#최대 공약수 구하기
    if a % i == 0 and b % i == 0:
        m = i

print(m)	#최대공약수 출력
print(m * (a // m) * (b // m))	#최소 공배수 출력

 

프로그램 코드 설명

m은 최대 공약수를 저장하는 숫자이다.

최대 공약수는 두 숫자 중 작은 숫자까지 반복을 하면서 두 숫자가 동시에 나눠지는 숫자 중 가장 큰 값을 구하면 된다.

둘 중 작은 숫자를 선택하면 실행 시간이 좀 더 줄어들겠지만 저는 편의상 둘 중 앞에 등장하는 숫자를 이용하였습니다.

최대 공약수는 구한 그대로 출력을 해주고

최소 공배수는 최대 공약수 * (a // 최대 공약수) * (b // 최대 공약수) 로 구할 수 있습니다.