728x90
우선 최대 공약수를 구하기 위해 유클리드 호제법을 사용한다.
a>b 에 대해서 a를 b로 나눈 나머지가 r 이라 하면
a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다
이 성질을 이용아여 b를 r로 나눈 나머지 r'을 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 나왔을때 나누는 수가 a와 b의 최대 공약수가 된다.
그래서 위의 과정을 0이 될때까지 반복하도록 while문을 이용하였고
다음 최소 공배수는 두수를 곱하고 작은수로 나누면 나오게 된다.
728x90
'프로그래머스 C++' 카테고리의 다른 글
| 프로그래머스 3진법 뒤집기 (0) | 2023.10.03 |
|---|---|
| 프로그래머스 같은 숫자는 싫어 (0) | 2023.10.03 |
| 프로그래머스 직사각형 별찍기 (0) | 2023.10.03 |
| 프로그래머스 행렬의 덧셈 (0) | 2023.10.03 |
| 프로그래머스 문자열 다루기 기본 (0) | 2023.10.03 |
