C++ 배열에서 합성수의 개수와 합계 구하기

양의 정수로 이루어진 배열이 주어졌을 때, 배열에 포함된 합성수(composite number)의 개수와 합계를 계산하는 방법을 알아보겠습니다.

합성수란 무엇인가?

주어진 정수 집합에서 소수(prime number)가 아닌 수를 합성수라고 합니다. 단, 1은 합성수도 소수도 아니며 '단위수(unit)'로 분류됩니다. 즉, 1을 제외한 모든 자연수는 소수 또는 합성수 중 하나에 반드시 해당합니다.

참고로 100까지의 합성수는 다음과 같습니다.

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25,
26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44,
45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62,
63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80,
81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96,
98, 99, 100

예시

입력 − array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
출력 − 합성수의 총 개수: 5
      합성수의 합계: 37

설명 − 주어진 배열에서 합성수는 4, 6, 8, 9, 10입니다. 따라서 개수는 5개이며, 합계는 4+6+8+9+10 = 37입니다.

입력 − array[] = {1, 2, 3, 4, 5}
출력 − 합성수의 총 개수: 1
      합성수의 합계: 4

설명 − 주어진 배열에서 유일한 합성수는 4입니다. 따라서 개수는 1개이고, 합계는 4입니다.

문제 해결 접근 방식

이 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

• 양의 정수로 이루어진 배열을 입력받습니다.
• 배열의 크기를 계산합니다.
• 합성수의 합계를 저장할 변수 sum을 초기화합니다.
• 배열에 있는 최댓값을 별도의 변수에 저장합니다.
• 에라토스테네스의 체(sieve)를 이용해 최댓값까지의 모든 소수를 미리 구합니다.
• 배열 전체를 순회하면서 각 숫자가 소수인지 확인합니다. 소수가 아니라면 합성수이므로, 합성수 개수를 1 증가시키고 해당 값을 합계에 더합니다.

소수 판별을 매번 새로 계산하는 대신 체를 한 번만 수행하면 되기 때문에, 배열의 요소가 많아져도 효율적으로 처리할 수 있다는 장점이 있습니다.

C++ 코드 예제

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 합성수의 개수를 찾아 반환하는 함수
int compcount(int ar[], int num, int* sum){
    // 배열에서 가장 큰 원소를 저장
    int max_val = *max_element(ar, ar + num);

    // 체(sieve)를 사용하여 max_val 이하의
    // 모든 소수를 찾음
    // 불리언 배열 "prime[0..n]"을 생성하며,
    // prime[i]의 값은 최종적으로 확정됨
    vector<bool> pr(max_val + 1, true);

    // 0과 1은 소수가 아니지만,
    // 합성수도 아니므로 true로 유지
    pr[0] = true;
    pr[1] = true;

    for (int p = 2; p * p <= max_val; p++){
        // prime[p]가 변경되지 않았다면 p는 소수
        if (pr[p] == true){
            // p의 모든 배수를 소수가 아닌 것으로 표시
            for (int i = p * 2; i <= max_val; i += p){
                pr[i] = false;
            }
        }
    }

    // arr[]에서 모든 합성수를 세고 합산
    int ans = 0;
    for (int i = 0; i < num; i++){
        if (!pr[ar[i]]){
            ans++;
            *sum = *sum + ar[i];
        }
    }
    return ans;
}

// 드라이버 코드
int main(){
    int ar[] = { 1, 2, 3, 4, 5 };
    int num = sizeof(ar) / sizeof(ar[0]);
    int sum = 0;
    cout << "Count of Composite Numbers = " << compcount(ar, num, &sum);
    cout << "\nSum of Composite Numbers = " << sum;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of Composite Numbers = 1
Sum of Composite Numbers = 4

이처럼 에라토스테네스의 체를 활용하면 배열을 한 번만 순회하면서 합성수의 개수와 합계를 동시에 구할 수 있으며, 시간 복잡도는 O(N log log N) 수준으로 매우 효율적입니다.