C++로 모든 쌍의 합이 소수가 되는 가장 큰 부분집합 찾기

이 글에서는 주어진 배열에서 모든 쌍의 합이 소수(prime number)가 되도록 만들 수 있는 가장 큰 부분집합을 찾는 방법을 다룹니다. 배열 원소의 최댓값은 100000이라고 가정합니다.

문제 예시

입력: nums[ ] = { 3, 2, 1, 1 }
출력: size = 3, subset = { 2, 1, 1 }
설명:
만들 수 있는 부분집합은 {3, 2}, {2, 1}, {2, 1, 1}입니다.
{2, 1, 1}에서 쌍 (2, 1)의 합은 3으로 소수이고,
쌍 (1, 1)의 합은 2 역시 소수입니다.

입력: nums[ ] = { 1, 4, 3, 2 }
출력: size = 2, subset = { 1, 4 }
설명:
만들 수 있는 부분집합은 {1, 4}, {4, 3}, {3, 2}로 모두 크기가 2입니다.
따라서 아무거나 선택할 수 있으며, 예를 들어 1 + 4 = 5는 소수입니다.

풀이 접근 방법

어떤 쌍의 합이 소수인지 판별하기 전에, 먼저 그 합이 홀수인지 짝수인지 확인해야 합니다. 짝수 중에서 소수는 2뿐이기 때문입니다. 그리고 두 수의 합이 짝수가 되려면 두 수가 모두 홀수이거나 모두 짝수여야 합니다.

이 문제에서는 세 개의 수 x, y, z를 생각해 볼 수 있는데, 이 중 임의의 두 수는 같은 홀짝성을 가져야 합니다. 그런 다음 이 부분집합에 대해 소수 합 조건을 검사하는데, 가능한 경우는 다음과 같습니다.

부분집합에 여러 개의 1과 다른 숫자들이 포함되어 있고, 각 숫자 NUM에 대해 NUM + 1이 소수인 경우
부분집합이 두 개의 숫자만 포함하며, 그 합이 소수인 경우

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
#define M 100001
bool check_prime[M] = { 0 };
int sieve_of_eratosthenes(){
    for (int p = 2; p * p < M; p++){
        // 아직 표시되지 않았다면 표시
        if (check_prime[p] == 0){
            // p의 모든 배수를 갱신
            for (int i = p * 2; i < M; i += p)
                check_prime[i] = 1;
        }
    }
    return 0;
}
int main(){
    sieve_of_eratosthenes();
    int nums[] = { 3, 2, 1, 1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int ones = 0;
    for (int i = 0; i < n; i++)
        if (nums[i] == 1)
            ones++;
    // 1이 존재하고 0보다 큰 다른 원소도 있는 경우
    if (ones > 0){
        for (int i = 0; i < n; i++){
            // nums[i] + 1이 소수인지 확인
            if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){
                cout << ones + 1 << endl;
                // 모든 1과 nums[i]를 함께 출력
                for (int j = 0; j < ones; j++)
                    cout << 1 << " ";
                cout << nums[i] << endl;
                return 0;
            }
        }
    }
    // 부분집합이 1로만 구성된 경우
    if (ones >= 2){
        cout << ones << endl;
        for (int i = 0; i < ones; i++)
            cout << 1 << " ";
        cout << endl;
        return 0;
    }
    // 1이 없는 경우
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            // 합이 소수인 정수 쌍 탐색
            if (check_prime[nums[i] + nums[j]] == 0){
                cout << 2 << endl;
                cout << nums[i] << " " << nums[j] << endl;
                return 0;
            }
        }
    }
// 배열에 원소가 하나뿐인 경우
    cout << -1 << endl;
    return 0;
}

실행 결과

3
1 1 2

코드 동작 설명

먼저 배열 안에 있는 1의 개수를 셉니다.
1이 하나 이상 있다면 배열을 순회하면서 1이 아닌 각 원소에 대해 nums[i] + 1이 소수인지 확인합니다. 소수라면 부분집합의 크기(ones + 1)를 출력하고, 모든 1과 해당 숫자를 함께 출력합니다.
배열이 1로만 구성되어 있다면, 모든 쌍의 합이 2(소수)가 되므로 전체 1을 출력합니다.
1이 하나도 없다면, 배열의 모든 쌍을 검사하여 합이 소수가 되는 쌍을 찾습니다.
위 조건 어느 것도 만족하지 않으면 -1을 출력합니다.

마무리

이번 글에서는 주어진 배열에서 모든 쌍의 합이 소수가 되는 가장 큰 부분집합을 찾는 문제를 살펴보았습니다. 에라토스테네스의 체(Sieve of Eratosthenes)를 활용해 소수를 미리 판별하고, 배열 내 1의 개수를 확인하는 방식으로 문제를 해결했습니다. 이 알고리즘은 C++뿐 아니라 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 튜토리얼이 여러분에게 도움이 되기를 바랍니다.