백준 2609번 c++ 문제 풀이

[문제]

[결과]

[해설]

유클리드 호제법(유클리드 알고리즘)은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 두 수가 서로 상대방의 수를 나누어서 결과적으로 원하는 수를 얻는 알고리즘을 의미한다.

원리는 이렇다.

큰 수를 작은 수로 나눈다 -> 나누는 수를 나머지로 계속 나눈다 -> 나머지가 0이 나올 때까지 반복한다.

-> 나머지가 0이 나온다면, 그때 나누는 수가 최대공약수이다.