C++ เซ็ตย่อยที่ใหญ่ที่สุดโดยมีผลรวมของทุกคู่เป็นไพร์ม

เพื่อหาเซตย่อยที่ใหญ่ที่สุดจากอาร์เรย์ที่กำหนดซึ่งผลรวมของทุกคู่เป็นจำนวนเฉพาะ สมมติว่าองค์ประกอบสูงสุดคือ 100000 ตัวอย่างเช่น −

Input: nums[ ] = { 3, 2, 1,1 }
Output: size = 3, subset = { 2, 1, 1 }
Explanation:
Subsets can be formed: {3, 2}, {2, 1} and { 2, 1, 1},
In {2, 1, 1} sum of pair (2,1) is 3 which is prime,
and the sum of pairs (1,1) is 2 which is also a prime number.

Input: nums[ ] = {1, 4, 3, 2}
Output: size = 2, subset = {1, 4}
Explanation:
subset can be formed: {1, 4}, {4, 3}, and {3, 2}
All are of size 2 so we can take any subset like 1 + 4 =5 which is a prime number.

แนวทางในการหาแนวทางแก้ไข

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

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

• เซตย่อยประกอบด้วยตัวเลขของ 1 และจำนวนอื่นๆ ที่ NUM + 1 ควรเป็นจำนวนเฉพาะ

• หรือถ้าเซตย่อยมีเพียงสองตัวเลขซึ่งผลรวมเป็นจำนวนเฉพาะ

ตัวอย่าง

 #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 it is not marked then mark
        if (check_prime[p] == 0){
            // Update all multiples of 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++;
    // If ones are present and
    // elements greater than 0 are also present
    if (ones > 0){
        for (int i = 0; i < n; i++){
            //checking whether num + 1 is prime or not
            if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){
                cout << ones + 1 << endl;
                // printing all the ones present with nums[i]
                for (int j = 0; j < ones; j++)
                cout << 1 << " ";
                cout << nums[i] << endl;
                return 0;
            }
        }
    }
    // If subsets contains only 1's
    if (ones >= 2){
        cout << ones << endl;
        for (int i = 0; i < ones; i++)
            cout << 1 << " ";
        cout << endl;
        return 0;
    }
    // If no ones are present.
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            // searching for pair of integer having sum prime.
            if (check_prime[nums[i] + nums[j]] == 0){
                cout << 2 << endl;
                cout << nums[i] << " " << nums[j] << endl;
                return 0;
            }
        }
    }
// If only one element is present in the array.
    cout << -1 << endl;
    return 0;
}

ผลลัพธ์

3
1 1 2

คำอธิบายของโค้ดด้านบน

• อันดับแรก เรากำลังตรวจสอบจำนวนในอาร์เรย์

• หากมากกว่า 0 ให้ข้ามผ่านอาร์เรย์และตรวจสอบองค์ประกอบอื่นที่ไม่ใช่ 1 ว่า nums[i] + 1 เป็นจำนวนเฉพาะหรือไม่ ถ้าใช่ ให้พิมพ์จำนวนรวมของ (อัน + 1) เป็นขนาดของชุดย่อยและจำนวนทั้งหมดที่มีตัวเลข

• หากอาร์เรย์ที่ระบุมีเพียงอาร์เรย์เดียว ให้พิมพ์ทั้งหมดเนื่องจากผลรวมของคู่ทั้งหมดจะเป็น 2 (ไพรม์)

• หากไม่มีใครอยู่ ให้ตรวจสอบทุกคู่ในอาร์เรย์ด้วย sum prime

• พิมพ์อื่น -1.

บทสรุป

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