[BOJ][C++] 백준 2609번 최대공약수와 최소공배수
Updated:
2609번 최대공약수와 최소공배수
1. 문제 정보
백준 온라인 저지 [2609번 최대공약수와 최소공배수] 문제의 링크입니다.
문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
예제 입력1
24 18
예제 출력1
6
72
시간 / 메모리 제한
1초 / 128MB
2. 생각
-
두 수를 입력받아 두 수의 최대공약수와 최소 공배수를 구하는 문제입니다.
최대공약수와 최소 공배수의 개념을 프로그래밍으로 옮기면 됩니다. -
먼저, 최대 공약수는 두 수의 약수(대상이 되는 수를 나누어 떨어지게 하는 수)중 최대 값을 구하는 것이므로 약수가 될 후보 i를 입력 받은 두 수중 작은 값까지 증가시키며 i가 두 수를 나누는지 확인합니다.
마지막에 수정 된 값이 최대 공약수입니다. -
다음으로, 최소 공배수는 두 수의 배수(대상이 되는 수를 곱하여 만들 수 있는 수)중 가장 작은 것을 구하는 것이므로 배수가 될 후보 i를 입력받은 두 수중 작은 값 부터 증가시키며 두 수가 i를 나눌 수 있는지 확인합니다.
가장 처음에 수정된 값이 최소공배수입니다.
3. 소스코드 (C++)
