유클리드 호제법1 [알고리즘] 유클리드 호제법 #c언어 [유클리드 호제법] 유클리드 호제법 : 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나.- 명시적으로 기술된 가장 오래된 알고리즘으로 알려져있다.- 기원전 300년경에 쓰인 유클리드의 제 7권, 명제 1부터 3까지에 해당 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘 알고리즘- 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하자 (단, a > b)- a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.- 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복- 이때 나머지가 0이 된다면 나누는 수가 a와 b의 최대공약수이다. [알고리즘]- 입력으로 두 수 m, n(m>n)을 입력받는다... 2018. 9. 26. 이전 1 다음