C++ Tập con lớn nhất với tổng mọi cặp là số nguyên tố

Tìm tập con lớn nhất của mảng sao cho tổng của mọi cặp trong tập con là số nguyên tố. Giả sử phần tử tối đa 100000. Ví dụ:

Input: {3,2,1,1} → Output: size=3, subset={2,1,1}
Giải thích: (2,1)=3 (nguyên tố), (1,1)=2 (nguyên tố)

Input: {1,4,3,2} → Output: size=2, subset={1,4}
Giải thích: 1+4=5 (nguyên tố)

Phương pháp giải

Tổng 2 số là nguyên tố chỉ khi tổng lẻ (trừ 2). Do đó tập con chỉ chứa số chẵn + số lẻ, hoặc chỉ chứa 1. Các trường hợp:

1. Có số 1: tìm x≠1 sao cho x+1 nguyên tố → tập con = tất cả 1 + x
2. Chỉ có 1: tất cả 1 (1+1=2 nguyên tố)
3. Không có 1: tìm cặp (x,y) sao cho x+y nguyên tố

Dùng sàng Eratosthenes kiểm tra nguyên tố.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

#define M 100001
bool is_composite[M] = {0};

int sieve() {
    for (int p=2; p*p<M; p++)
        if (!is_composite[p])
            for (int i=p*2; i<M; i+=p)
                is_composite[i] = 1;
    return 0;
}

int main() {
    sieve();
    int nums[] = {3,2,1,1};
    int n = sizeof(nums)/sizeof(nums[0]);
    int ones = 0;
    for (int x: nums) if (x==1) ones++;

    if (ones > 0) {
        for (int x: nums)
            if (x!=1 && !is_composite[x+1]) {
                cout << ones+1 << "\n";
                for (int i=0; i<ones; i++) cout << 1 << " ";
                cout << x << "\n";
                return 0;
            }
    }
    if (ones >= 2) {
        cout << ones << "\n";
        for (int i=0; i<ones; i++) cout << 1 << " ";
        return 0;
    }
    for (int i=0; i<n; i++)
        for (int j=i+1; j<n; j++)
            if (!is_composite[nums[i]+nums[j]]) {
                cout << 2 << "\n" << nums[i] << " " << nums[j] << "\n";
                return 0;
            }
    cout << -1 << "\n";
    return 0;
}

Kết quả

3
1 1 2

Giải thích

• Sàng Eratosthenes đến 100000.
• Đếm số 1, xử lý 3 trường hợp theo thứ tự ưu tiên.

Kết luận

Đã giải bài toán tập con lớn nhất tổng cặp là nguyên tố bằng phân tích chẵn/lẻ và sàng Eratosthenes. Code C++ áp dụng cho C, Java, Python. Hy vọng hữu ích.