[Algorithm] BasicGCD

◈ 최대공약수 

주어진 두 정수의 약수 중에서 가장 큰 공통인 약수이다. 

예를 들어, 12와 18의 최대공약수를 구해보자.

12 →  1 2 3 4 6 12

18 →  1 2 3 6 9 18 

◈ 최대공약수 관련 법칙

1. 만약 a>b 라면, GCD(a,b) = GCD(a-b,b);

2. GCD(a,0) = a

◈ 유클리드 알고리즘

GCD(170, 20) 

= GCD(150,20)

= GCD(130,20)

= ...

= GCD(10,20)

= GCD(0,10)

= 10 

◈ 개선된 유클리드 알고리즘

위의 유클리드 알고리즘은 뺄셈을 기반으로 한 알고리즘이다. 하지만 1000, 10000 과 같은 큰 수일 경우는 %을 이용하는 알고리즘이 있다.

GCD(a,b) = GCD(a%b,b) = GCD(b, a%b)

<코드>

#include<stdio.h>

int n;

int BasicGCD(int a, int b){

  int mod;

  while(b){

    mod = a%b;

    a = b;

    b = mod;

  }

  return a;

}

int main()

{

  int n,m;

  scanf("%d %d",&n,&m);

  

  printf("%d",BasicGCD(n,m));

  

  return 0;

}