[백준_2609] 최대공약수와 최소공배수

문제 보기: https://www.acmicpc.net/problem/2609

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

문제

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

 

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000 이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

풀이 과정

1. 처음에는 최대 공약수를 찾는 것 부터 시작했다. 두 수중 작은 수의 값이 최대 공약수가 될 수 있는 가장 큰 값이라는 생각부터 시작

2. for문을 돌려서 가장 큰값부터 1씩 내려가면서 나누어 떨어지는지를 판별

3. 두 숫자 다 나누어 떨어진다면 해당 값을 최대 공약수에 저장하고 for문을 종료 

4. 최대 공약수를 구하였다면 최대공약수 X 최소공배수 = 숫자 A X 숫자 B를 이용해서 최소공배수까지 구해주면 되겠다.

 

코드

a, b = map(int, input().split())

greatest_common_factor = 1

if a < b:
    numbers = a
else:
    numbers = b

for number in range(numbers):
    divide = (numbers - number)
    if a % divide == 0 and b % divide == 0:
        greatest_common_factor = divide
        break

least_common_multiple = int((a * b) / greatest_common_factor)

print(greatest_common_factor)
print(least_common_multiple)