배열에서 소수의 곱과 비소수의 곱의 절대 차이 구하는 방법

이 글에서는 배열에 포함된 모든 소수(prime number)의 곱과 모든 비소수(non-prime)의 곱 사이의 절대 차이를 구하는 방법을 알아봅니다.

이 문제를 해결하려면 먼저 주어진 수가 소수인지 아닌지를 판별해야 합니다. 소수 판별 방법 중 가장 기본적인 방법은 해당 수가 2부터 그 수의 제곱근(√n) 사이의 어떤 수로도 나누어 떨어지지 않는지 확인하는 것입니다. 이 과정은 하나의 수에 대해 O(√n)의 시간 복잡도를 가집니다. 이후 소수와 비소수의 곱을 각각 계산한 뒤, 두 값의 절대 차이를 구하면 됩니다.

알고리즘

diffPrimeNonPrimeProd(arr)

begin
   prod_p := 배열 arr에 있는 모든 소수의 곱
   prod_np := 배열 arr에 있는 모든 비소수의 곱
   return |prod_p – prod_np|
end

C++ 구현 예제

#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n){
   for(int i = 2; i<=sqrt(n); i++){
      if(n % i == 0){
         return false; //소수가 아님
      }
   }
   return true; //소수임
}
int diffPrimeNonPrimeProd(int arr[], int n) {
   int prod_p = 1, prod_np = 1;
   for(int i = 0; i<n; i++){
      if(isPrime(arr[i])){
         prod_p *= arr[i];
      } else {
         prod_np *= arr[i];
      }
   }
   return abs(prod_p - prod_np);
}
main() {
   int arr[] = { 4, 5, 3, 8, 13, 10};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Difference: " << diffPrimeNonPrimeProd(arr, n);
}

실행 결과

Difference: 125

동작 원리 설명

예제 배열 { 4, 5, 3, 8, 13, 10 }을 기준으로 살펴보겠습니다.

• 소수: 5, 3, 13 → 곱 = 5 × 3 × 13 = 195
• 비소수: 4, 8, 10 → 곱 = 4 × 8 × 10 = 320

따라서 절대 차이는 |195 − 320| = 125가 됩니다.

참고 사항

• 숫자 1은 소수도 비소수(합성수)도 아니지만, 일반적으로 이 문제에서는 비소수로 분류하여 처리합니다.
• 배열의 크기가 크거나 요소 값이 클 경우 곱이 int 범위를 초과할 수 있으므로, 실제 구현에서는 long long 같은 더 넓은 범위의 자료형을 사용하는 것이 안전합니다.
• 배열의 모든 요소에 대해 소수 판별을 수행하므로 전체 시간 복잡도는 O(n√m)입니다. 여기서 m은 배열 요소의 최댓값입니다.