반응형 최소공배수1 [C++] 유클리드 호제법을 사용해 최대공약수 구하기 유클리드 호제법 유클리드 호제법이란 2개의 자연수를 이용해 최대공약수를 구하는 알고리즘이다. 유클리드 호제법을 사용해 최대공약수를 구하는 방법 두 자연수를 각각 a와 b라고 하고 a >= b 일 때 a % b = c 계산을 한다. c가 0이 아니라면 b % c 계산을 진행한다. 나머지 값이 0이 될 때까지 반복한다. 나머지 값이 0이 되었을 때 나누는 수의 값이 두 자연수의 최대공약수이다. 예시) 78696와 19332의 최대공약수 구하기 / 최대공약수는 36이다. 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 ＋ 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 ＋ 0 출처) 위키백과 최대공약수 구하기 유클리드 .. 2024. 1. 19. 이전 1 다음 반응형
