유클리드 호제법

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나이다.

 

간단하게 정리하자면

 

1. 큰 수를, 작은 수로 나눈다

2. 나누는 수를, 나머지로 계속 나눈다

 

나머지가 0이 나올 때,

나누는 수가 최대공약수이다

 

Ex) 1512, 1008의 최대공약수를 구하라

1. 1512 / 1008 = 1... 504

2. 1008 / 504 = 2... 0

따라서 최대공약수는 나누는 수였던 504가 된다.

 

 

식과 증명에 관해선 다른 블로그 글을 첨부해둔다

https://m.blog.naver.com/PostView.naver?blogId=gdpresent&logNo=222452479379&navType=tl 

최대공약수와 최소공배수(feat. 유클리드 호제법(Euclidean Algorithm)) [내가 공부한 파이썬 #6.]