유클리드 호제법
최대공약수 알고리즘, 유클리드의 호제법 +최소공배수 구하기
1. 유클리드 호제법이란 두 자연수의 최대공약수를 구하는 알고리즘 중 하나 유클리드의 저서 《기하학원본》에 기재되어 있는 최대공약수를 구하는 방법 호제법 또는 연제법 이라고 한다 사용되는 성질 a를 b로 나눈 나머지 = c 이면 a, b의 최대공약수는 b, c의 최대공약수와 같다 알고리즘 두 자연수 또는 다항식 a,b의 최대공약수를 구하는 데 있어, 자연수일 때는 a > b, 다항식일 때는 a의 차수가 b의 차수 이상이라 하고, 다음과 같이 나눗셈을 실행한다 b를 c로 나눈 나머지 = c' 를 구하고 c'를 d로 나눈 나머지 = ... 위 과정을 반복하여 나머지가 0이 되었을 때의 '나누는 수'가 a와 b의 최대공약수이다. 2. 예시 78696과 19332의 최대공약수 구하기 78696＝19332×4＋1..
유클리드 호제법
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)) [내가 공부한 파..