배열에서 소수의 합과 비소수의 합의 절대 차이 구하기

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

문제 접근 방식

이 문제를 해결하려면 먼저 각 숫자가 소수인지 아닌지를 판별해야 합니다. 가장 대표적인 소수 판별 방법은 해당 수가 2부터 그 수의 제곱근(√n) 사이의 어떤 수로도 나누어 떨어지지 않는지를 검사하는 것입니다.

예를 들어 n이 소수인지 확인할 때 2부터 n-1까지 모두 검사하면 O(n)의 시간이 걸리지만, 제곱근까지만 검사하면 O(√n)의 시간 복잡도로 충분합니다. 이는 n = a × b 형태로 나타낼 수 있다면 a와 b 중 하나는 반드시 √n 이하라는 성질 때문입니다.

소수 판별이 완료되면 소수들의 합(sum_p)과 비소수들의 합(sum_np)을 각각 계산한 뒤, 두 값의 절대 차이를 반환하면 됩니다.

알고리즘

diffPrimeNonPrimeSum(arr)

begin
    sum_p := 배열 arr에서 모든 소수의 합
    sum_np := 배열 arr에서 모든 비소수의 합
    return |sum_p – sum_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 diffPrimeNonPrimeSum(int arr[], int n) {
    int sum_p = 0, sum_np = 0;
    for (int i = 0; i < n; i++) {
        if (isPrime(arr[i])) {
            sum_p += arr[i];
        } else {
            sum_np += arr[i];
        }
    }
    return abs(sum_p - sum_np);
}

main() {
    int arr[] = { 5, 8, 9, 6, 21, 27, 3, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Difference: " << diffPrimeNonPrimeSum(arr, n);
}

실행 결과

Difference: 50

결과 분석

예제 배열 {5, 8, 9, 6, 21, 27, 3, 13}을 살펴보면 다음과 같습니다.

• 소수: 5, 3, 13 → 합계 = 21
• 비소수: 8, 9, 6, 21, 27 → 합계 = 71

따라서 절대 차이는 |21 − 71| = 50이 됩니다.

시간 복잡도

배열의 크기를 n이라 하고, 각 원소의 최댓값을 m이라고 할 때 전체 시간 복잡도는 O(n√m)입니다. 각 원소에 대해 O(√m)의 소수 판별을 수행하기 때문입니다. 만약 같은 범위의 수를 반복적으로 판별해야 한다면 에라토스테네스의 체(Sieve of Eratosthenes)를 활용해 미리 소수 테이블을 만들어 두는 것이 더 효율적입니다.