유클리드 호제법1 [Algorithm] 유클리드 호제법 (최대공약수 & 최소공배수 구하기) 유클리드 호제법 유클리드 호제법이란, 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다. 의무교육 과정에서 최대공약수를 구하는 방법을 두가지 배울텐데 소인수분해와 호제법을 배운다. 호제법을 쓰다보면 위 경우처럼 수가 크면 계산이 복잡해지고, 약수를 한번에 찾기가 힘든 경우가 있다. 이 때, 유클리드 호제법을 이용해서 쉽게 구할수 있다. 유클리드 호제법은 두 정수의 최대공약수를 빠르게 구하는 방법이다. 하나만 기억해야하면 "A > B 일때, A와 B의 최대공약수는 B와 나머지 R의 최대공약수와 같다." 큰 수(A)를 작은 수(B)로 나눈다. ( A > B ) 만약 나누고 난 나머지가 0 이라면 작은 수가 최대공약수이다. 만약 나머지가 0이 아니라면, 작은 수(B)를 나머지(R)로 계속 나눈다. 이를.. 2023. 3. 24. 이전 1 다음
