Java로 숫자의 고유한 소인수 곱 구하기

어떤 수의 고유한 소인수(Unique Prime Factors)란 해당 수를 나눌 수 있는 서로 다른 소수들을 의미합니다. 예를 들어 68은 2 × 2 × 17로 인수분해되므로 고유한 소인수는 2와 17이며, 이들의 곱은 34가 됩니다. 아래에서는 Java를 사용해 이 값을 구하는 방법을 살펴보겠습니다.

예제 코드

public class Demo {
   public static long prime_factors(int num){
      long my_prod = 1;
      for (int i = 2; i <= num; i++){
         if (num % i == 0){
            boolean is_prime = true;
            for (int j = 2; j <= i / 2; j++){
               if (i % j == 0){
                  is_prime = false;
                  break;
               }
            }
            if (is_prime){
               my_prod = my_prod * i;
            }
         }
      }
      return my_prod;
   }
   public static void main(String[] args){
      int num = 68;
      System.out.println("The product of unique prime factors is ");
      System.out.print(prime_factors(num));
   }
}

실행 결과

The product of unique prime factors is
34

코드 동작 원리

Demo 클래스 안에는 prime_factors라는 정적(static) 메서드가 정의되어 있습니다. 이 메서드는 매개변수로 전달받은 수의 소인수를 찾아 중복을 제거한 뒤, 그 곱을 변수에 저장하여 반환합니다. 전체적인 동작 과정은 다음과 같습니다.

1. 바깥쪽 반복문(i)이 2부터 num까지의 수를 하나씩 확인하며 num의 약수를 찾습니다.
2. 약수를 발견하면 안쪽 반복문(j)을 통해 해당 값이 소수인지 판별합니다.
3. 소수로 확인된 약수만 my_prod에 곱해집니다. 같은 소인수가 여러 번 나타나더라도 각 소수는 한 번만 곱해지므로 자연스럽게 '고유한' 소인수의 곱이 구해집니다.
4. main 메서드에서는 num을 68로 설정한 후 prime_factors 메서드를 호출하고, 그 결과를 콘솔에 출력합니다.

68의 경우 소인수는 2와 17이므로, 최종적으로 2 × 17 = 34가 출력됩니다.

참고 사항

위 코드는 이해하기 쉬운 직관적인 방식이지만, 이중 반복문을 사용하기 때문에 입력값이 커질수록 연산량이 늘어나는 단점이 있습니다. 따라서 매우 큰 수를 다룰 때는 소인수분해를 먼저 수행한 뒤 중복을 제거하는 방식처럼 더 효율적인 알고리즘을 적용하는 것이 좋습니다.