두 숫자의 공약수 개수를 구하는 Java 프로그램

이 글에서는 Java를 사용하여 두 숫자의 공약수 개수를 구하는 방법을 예제 코드와 함께 살펴봅니다. 핵심 아이디어는 유클리드 호제법으로 두 수의 최대공약수(GCD)를 먼저 구한 뒤, 해당 GCD의 약수 개수를 세는 것입니다. 두 수의 모든 공약수는 결국 최대공약수의 약수이기 때문에 이 방식은 매우 효율적입니다.

예제 코드

public class Demo{
   static int find_gcd(int val_1, int val_2){
      if (val_1 == 0)
      return val_2;
      return find_gcd(val_2%val_1,val_1);
   }
   static int common_divisors(int val_1,int val_2){
      int no = find_gcd(val_1, val_2);
      int result = 0;
      for (int i=1; i<=Math.sqrt(no); i++){
         if (no%i==0){
            if (no/i == i)
               result += 1;
            else
               result += 2;
         }
      }
      return result;
   }
   public static void main(String args[]){
      int val_1 = 68, val_2 = 34;
      System.out.println("The common divisors between the two numbers is ");
      System.out.println(common_divisors(val_1, val_2));
   }
}

실행 결과

The common divisors between the two numbers is
4

코드 동작 원리

Demo 클래스 안에는 두 개의 정적(static) 메서드가 정의되어 있습니다. 첫 번째 메서드 find_gcd는 재귀 호출을 활용한 유클리드 호제법으로 두 값의 최대공약수를 계산하여 반환합니다. 나머지가 0이 되는 시점에 재귀가 종료되며, 그때의 값이 곧 최대공약수입니다.

두 번째 메서드 common_divisors는 앞서 구한 최대공약수를 받아 1부터 그 제곱근(Math.sqrt(no))까지 반복하면서 약수를 탐색합니다. 반복 변수 i로 최대공약수를 나누었을 때 나머지가 0이라면 i는 약수입니다. 이때 no / i == i, 즉 제곱근과 같은 경우(완전제곱수)에는 중복되는 하나의 약수이므로 결과값을 1만큼 증가시키고, 그렇지 않으면 i와 no/i가 서로 다른 약수 쌍을 이루므로 결과값을 2만큼 증가시킵니다. 이처럼 제곱근까지만 검사하면 전체 범위를 순회하지 않고도 O(√n) 시간 복잡도로 약수의 개수를 구할 수 있습니다.

main 메서드에서는 두 숫자 68과 34를 초기화한 뒤 common_divisors 메서드를 호출하고, 그 결과를 화면에 출력합니다. 실제로 68과 34의 최대공약수는 34이며, 34의 약수는 1, 2, 17, 34로 총 4개이므로 실행 결과로 4가 출력됩니다.