[java] 최대공약수 구하기(gcd)

최대 공약수 구하기

 

 

백준 1934번을 푸는 중 최대공약수를 구하는 방법을 몰라 공부하게 되었다.

 

백준 문제

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

 

최대 공약수 구하는 알고리즘은

유클리드 호제법 을 이용해서 최대공약수를 구한다.

 

이 방식은 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될때까지 작동하여 최대공약수를 구하는 방식입니다.

 

 

1. 재귀함수 방법

// 재귀 방식
public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

 

 

2. 반복문 방법

// 반복문 방식
public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

 

최대 공약수를 구할수 있다.