최대공약수 - 유클리드 알고리즘
·
코딩테스트/JAVA
- 문제설명 최대공약수란 어떤 두 개 이상의 자연수들이 있을 때, 두 수의 공통된 약수 중 가장 큰 수를 말합니다. 서로 다른 두 자연수 N, M이 주어졌을 때, 두 수의 최대공약수를 출력하는 프로그램을 만드세요. - 입출력 예 입력 #1124 512 입력 #214 18 - 입력값 설명첫째 줄에 서로 다른 두 자연수 N ,M이 공백을 두고 주어집니다. (1 ≤ N ≤ 100,000) (1 ≤ M ≤ 100,000) 출력 #14 - 출력 #22 - 출력값 설명두 자연수 N, M의 최대공약수를 출력합니다. - 풀이 과정결론부터 말하자면 최대공약수를 출력하는데 있어서 유클리드 알고리즘의 효율성이 높다는 것을 알게되었습니다. 최대공약수는 두 수(혹은 그 이상)가 공통으로 가지는 약수 중 가장 큰 수를 의미..