꼬물이

유클리드 호제법 본문

수학

유클리드 호제법

빨간고양이 2018. 6. 28. 15:43
  • 정리 (유클리드 호제법)

두 개의 수 $a$ 와 $b$ 의 최대공약수를 계산하려면, ${r}_{-1} = a,$ ${r}_{0} = b$ 라 놓고, 다음의 몫과 나머지 구하는 과정

 ${r}_{i-1} = {q}_{i+1}\times {r}_{i}+{r}_{i+1}, \quad i = 0, 1, 2, \cdots$

을 계속하여 나머지 ${r}_{n+1}$이 $0$ 이 될 때까지 반복한다. 이때 0이 아닌 마지막 나머지 ${r}_{n}$이 $a$ 와 $b$ 의 최대공약수이다.


유클리드 호제법을 이용하여 최대공약수를 구하는 프로그램입니다. 답 및 풀이를 볼 수 있습니다.

2개의 정수를 입력하세요.

 

최대공약수 :

 


'수학' 카테고리의 다른 글

유클리드 호제법  (0) 2018.06.28
0 Comments
댓글쓰기 폼