# 문제 출제 사이트
https://www.acmicpc.net/problem/2609
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
# 문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
# 입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000 이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
# 출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
# 제출한 소스코드(맞은 것)
# 참고한 사이트
https://artiper.tistory.com/23
백준 2609번 C/C++
2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수와 최소공배수 문
artiper.tistory.com
- 유클리드 호제법으로 최대공약수를 구하는 공식
- 최소공배수를 구하는 공식
유클리드 호제법이 아닌 인수분해로 문제를 풀게 되면 문제 발생
* 유클리드 호제법이란? => 링크
# 제출한 소스코드2(틀린 것)
최대공약수, 최대공약수 구하는 방법
이번에는 최대공약수에 대해서 더 알아볼 거예요. 이제까지는 최대공약수를 구할 때 일단 약수를 모두 구해놓고 그중에서 가장 큰 걸 찾았잖아요. 약수를 모두 구해야 하는 아주 귀찮은 방법이
mathbang.net
위 링크를 참고해서 공식을 그대로 코드로 옮겨 봤었다.
예제로 제공되는 것에는 원하는 정답이 나왔지만 제출 후에 틀렸다는 것을 알게 되었다.
결국 유클리드 호제법을 사용해서 문제를 해결했다.
