[알고리즘] 최대 공약수 (GCD)

최대 공약수

• 최대 공약수란 두 수 (n과 r)의 약수들 중 공통된 약수의 최대 값
• 4와 8의 최대 공약수는
  • 4의 약수 1 2 4 
  • 8의 약수 1 2 4 8
  • 공통된 숫자중 4가 제일 크기 떄문에  4이다.

 

유클리드 호제법을 재귀함수로 최대 공약수를 간단하게 구할 수 있다.

main{

int gcdNum = gcd(4, 8);
print(gcdNum); // 4

}

// 유클리드 호제법
int gcd(int n, int m) {

    if (m == 0) return n;
    return gcd(m, n % m);
    
}