Java로 두 숫자의 최대공약수(GCD) 구하는 방법

이 글에서는 Java를 사용하여 두 숫자의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법을 알아봅니다. 최대공약수란 두 숫자를 모두 나누어 떨어지게 하는 수 중 가장 큰 수를 의미합니다.

입력 · 출력 예시

예를 들어 아래와 같은 두 개의 숫자가 주어졌다고 가정해 보겠습니다.

첫 번째 숫자 : 18
두 번째 숫자 : 24

이때 기대되는 출력 결과는 다음과 같습니다.

두 숫자의 GCD : 6

알고리즘

1단계 – 시작
2단계 – 세 개의 정수형 변수(input_1, input_2, gcd)를 선언한다
3단계 – 사용자에게 두 개의 정수 값 입력을 요청하거나, 코드에 값을 직접 지정한다
4단계 – 값을 읽어 들인다
5단계 – 현재 숫자가 두 수(x, y)를 모두 나누어 떨어지게 하는지 확인하고, 그렇다면 변수에 저장한다
6단계 – 마지막으로 저장된 'i' 값을 두 숫자의 GCD로 출력한다
7단계 – 종료

예제 1 – 사용자 입력값으로 GCD 구하기

아래 예제에서는 Scanner 클래스를 사용해 사용자로부터 두 개의 정수를 입력받은 후 GCD를 계산합니다.

import java.util.Scanner;
public class GCD{
   public static void main(String[] args){
      int input_1 , input_2 , gcd ;
      Scanner reader = new Scanner(System.in);
      System.out.println("A reader object has been defined ");
      System.out.print("Enter a first number: ");
      input_1 = reader.nextInt();
      System.out.print("Enter a second number: ");
      input_2 = reader.nextInt();
      gcd = 1;
      for(int i = 1; i <= input_1 && i <= input_2; i++){
         if(input_1%i==0 && input_2%i==0)
         gcd = i;
      }
      System.out.printf("
The GCD of %d and %d is: %d", input_1, input_2, gcd);
   }
}

출력 결과

A reader object has been defined
Enter a first number: 24
Enter a second number: 18
The GCD of 24 and 18 is: 6

예제 2 – 미리 정의된 값으로 GCD 구하기

아래 예제에서는 두 정수가 코드 안에 미리 정의되어 있으며, 이 값을 콘솔에 출력한 뒤 GCD를 계산합니다.

public class GCD{
   public static void main(String[] args){
      int input_1 , input_2 , gcd ;
      input_1 = 12;
      input_2 = 18;
      gcd = 1;
      System.out.print("The first number is " + input_1);
      System.out.print("
The second number is " + input_2);
      for(int i = 1; i <= input_1 && i <= input_2; i++){
         if(input_1%i==0 && input_2%i==0)
         gcd = i;
      }
      System.out.printf("
The GCD of %d and %d is: %d", input_1, input_2, gcd);
   }
}

출력 결과

The first number is 12
The second number is 18
The GCD of 12 and 18 is: 6

참고: 더 효율적인 방법 – 유클리드 호제법

위 예제들은 1부터 두 수 중 작은 값까지 반복문을 실행하며 모든 약수를 하나씩 확인하기 때문에, 숫자가 커지면 연산 시간이 길어질 수 있습니다. 실무에서는 유클리드 호제법(Euclidean Algorithm)을 사용하는 것이 더 효율적입니다. 이 방법은 두 수 a, b(a > b)에 대해 a를 b로 나눈 나머지 r을 구하고, 다시 b와 r에 대해 같은 과정을 반복하여 나머지가 0이 될 때의 나누는 수가 곧 최대공약수가 된다는 원리를 이용합니다.