본문 바로가기

Daylogs/Logic

최대공약수 구하기(유클리드 호제법)

발생일: 2011.05.18

문제:
자연수 m과 n이 있다. 이 두 수의 최대공약수는 어떻게 구할 수 있을까~?

해결책:
유클리드 호제법

int m = 128,
    n = 24,
    k;

do {
    k = m % n;
    m = n;
    n = k;
} while (k != 0);

System.out.print(m);



* 참고: Java의 BigInteger 클래스에 gcd() 메서드가 있기는 하다.