C++ Subset ใหญ่ที่สุดที่ผลรวมทุกคู่เป็นจำนวนเฉพาะ

เพื่อหา Subset ใหญ่ที่สุดจากอาร์เรย์ที่กำหนด ซึ่งผลรวมของทุกคู่เป็นจำนวนเฉพาะ (Prime) สมมติค่าสูงสุดคือ 100,000 เช่น

Input: nums[ ] = { 3, 2, 1, 1 } Output: size = 3, subset = { 2, 1, 1 } Explanation: Subsets ที่เป็นไปได้: {3, 2}, {2, 1} และ { 2, 1, 1} ใน {2, 1, 1} ผลรวมคู่ (2,1) คือ 3 เป็นเฉพาะ และผลรวม (1,1) คือ 2 ก็เป็นเฉพาะ
Input: nums[ ] = {1, 4, 3, 2} Output: size = 2, subset = {1, 4} Explanation: subset ที่เป็นไปได้: {1, 4}, {4, 3}, และ {3, 2} ทั้งหมดขนาด 2 สามารถเลือกได้ เช่น 1 + 4 = 5 เป็นเฉพาะ

วิธีการแก้ปัญหา

เพื่อตรวจสอบว่าคู่เป็นเฉพาะ เราต้องเช็คว่าผลรวมเป็นคี่หรือคู่ เพราะเลขคู่ไม่ใช่เฉพาะ (ยกเว้น 2) ผลรวมของสองจำนวนจะเป็นคี่ถ้าตัวหนึ่งคี่อีกตัวคู่

ในปัญหานี้ เราจะพิจารณา 3 กรณี: x, y, z โดยสองจำนวนใดๆ ต้องเป็นคู่หรือคี่พร้อมกัน แล้วตรวจสอบ Subset นี้สำหรับคู่ที่ผลรวมเป็นเฉพาะ ซึ่งเป็นไปได้หาก

• Subset มีตัวเลข 1 จำนวนหนึ่ง และตัวเลขอื่นๆ ที่ NUM + 1 เป็นเฉพาะ
• หรือ Subset มีแค่สองตัวเลขที่ผลรวมเป็นเฉพาะ

ตัวอย่าง

#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){ 
            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++; 
    if (ones > 0){ 
        for (int i = 0; i < n; i++){ 
            if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){ 
                cout << ones + 1 << endl; 
                for (int j = 0; j < ones; j++) cout << 1 << " "; 
                cout << nums[i] << endl; 
                return 0; 
            } 
        } 
    } 
    if (ones >= 2){ 
        cout << ones << endl; 
        for (int i = 0; i < ones; i++) cout << 1 << " "; 
        cout << endl; 
        return 0; 
    } 
    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 ในอาร์เรย์
• ถ้ามีมากกว่า 0 ให้วนลูปตรวจสอบสมาชิกที่ไม่ใช่ 1 ว่า nums[i] + 1 เป็นเฉพาะไหม ถ้าใช่ พิมพ์ขนาด (ones + 1) และพิมพ์ 1 ทั้งหมดพร้อมตัวเลขนั้น
• ถ้าอาร์เรย์มีแค่ 1 อย่างเดียว ให้พิมพ์ 1 ทั้งหมด เพราะผลรวมทุกคู่จะเป็น 2 (เฉพาะ)
• ถ้าไม่มี 1 เลย ให้ตรวจสอบทุกคู่ในอาร์เรย์ว่าผลรวมเป็นเฉพาะไหม
• มิฉะนั้นพิมพ์ -1

สรุป

ในบทช่วยสอนนี้ เราอภิบัติปัญหาการหา Subset ใหญ่ที่สุดจากอาร์เรย์ที่กำหนด ซึ่งผลรวมของแต่ละคู่เป็นจำนวนเฉพาะ เราอภิบัติวิธีแก้ปัญหาด้วยการใช้ Sieve of Eratosthenes และตรวจสอบจำนวนเลข 1 ในอาร์เรย์ เรายังอภิบัติโปรแกรม C++ สำหรับปัญหานี้ ซึ่งสามารถทำได้กับภาษาอื่น เช่น C, Java, Python ฯลฯ หวังว่าจะเป็นประโยชน์