C++ Subset maksimum dengan jumlah setiap pasangan elemen ialah nombor perdana

Cari subset terbesar daripada tatasusunan yang diberikan dengan jumlah setiap pasangan elemen ialah nombor perdana. Katakan elemen maksimum ialah 100000, contohnya −

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.

Cara-cara mencari penyelesaian

Pertama, untuk menentukan sama ada pasangan nombor adalah perdana, kita perlu menyemak sama ada jumlahnya ganjil atau genap, kerana nombor genap bukan perdana kecuali 2. Juga, jika kedua-dua nombor adalah ganjil atau genap, jumlahnya mungkin genap.

Dalam masalah ini, kita akan mengambil tiga nombor, x, y dan z, mana-mana dua daripadanya hendaklah ganjil atau genap. Kami kemudiannya akan menyemak sama ada subset ini mengandungi pasangan jumlah perdana, yang mungkin boleh dilakukan jika:

• Subset mengandungi beberapa nombor 1 dan beberapa nombor lain dengan NUM + 1 sepatutnya nombor perdana.

• Atau jika subset mengandungi dua nombor sahaja, jumlahnya ialah nombor perdana.

Contoh

 #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&#39;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;
}

Output

3
1 1 2

Penerangan kod di atas

• Mula-mula kita semak nombor dalam array.

• Jika lebih daripada 0, ulangi tatasusunan dan semak sama ada setiap elemen kecuali 1 ialah nombor[i] + 1 ialah nombor perdana; jika ya, cetak jumlah bilangan (satu + 1) sebagai saiz subset dan nombor dengan Nombor itu semua 1.

• Jika tatasusunan yang diberikan mengandungi hanya 1, cetak kesemuanya kerana jumlah semua pasangan ialah 2 (nombor perdana).

• Jika tiada sesiapa yang hadir, pastikan jumlah setiap pasangan dalam tatasusunan adalah perdana.

• Cetak lain -1.

Kesimpulan

Dalam tutorial ini, kita membincangkan masalah di mana kita perlu mencari subset terbesar daripada tatasusunan yang diberikan di mana jumlah setiap pasangan ialah nombor perdana. Kami membincangkan cara untuk menyelesaikan masalah ini dengan bantuan Sieve of Eratosthenes dan menyemak nombor dalam tatasusunan. Kami juga membincangkan program C++ untuk menyelesaikan masalah ini, yang boleh kami laksanakan menggunakan bahasa pengaturcaraan seperti C, Java, Python, dll. Kami harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci C++ Subset maksimum dengan jumlah setiap pasangan elemen ialah nombor perdana. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!