- 유클리드 알고리즘(Euclideans Algorithm)

  : a, b, q, r 이 정수라고 가정할 때

    a = b * q + r  =>  gcd(a,b) = gcd(b,r)

    의 원리를 이용해 a,b의 최대공약수를 구한다.


- C/C++소스코드

#include <stdio.h>


int Eucl(int, int); //유클리드 알고리즘을 구현한 함수의 정의


int main(void){

int a, b, big; // a, b 입력받을 정수, big 수를 비교할 사용할 변수

int gcm; // 유클리드 알고리즘 함수의 반환값을 받기 위한 변수

scanf_s("%d %d", &a, &b); // a, b 두수를 입력 받는다.

   

if (a>b){ // a, b 비교해서 b쪽에 수가 오도록 정렬하는 조건문

big = a;

a = b;

b = big;

}


printf("%d", gcm = Eucl(a, b));

return 0;

}


int Eucl(int a, int b){

int remain; // 나머지를 받기 저장하기 위한 변수

remain = b%a; // b a 나눈 나머지를 remain 저장한다.


if (remain == 0) // remain 0이라는 것은 a a, b  최대공약수라는 것을 의미한다.
    return a;
else

return Eucl(remain, a); // 최대공약수를 찾지 못했으므로 유클리드 알고리즘을 반복한다.

}


+ Recent posts