C++ Sous-ensemble maximum où la somme de chaque paire d'éléments est un nombre premier

Trouvez le plus grand sous-ensemble du tableau donné où la somme de chaque paire d'éléments est un nombre premier. Supposons que l'élément maximum soit 100000, par exemple −

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.

Façons de trouver la solution

Premièrement, pour déterminer si la paire de nombres est première, nous devons vérifier si leur somme est impaire ou paire, puisque les nombres pairs ne sont pas premiers sauf 2. De plus, si les deux nombres sont pairs ou impairs, leur somme peut être paire.

Dans ce problème, nous prendrons trois nombres, x, y et z, deux d'entre eux devant être impairs ou pairs. Nous vérifierons ensuite si ce sous-ensemble contient des paires de sommes premières, ce qui peut être possible si :

• Le sous-ensemble contient des nombres de 1 et d'autres nombres où NUM + 1 doivent être des nombres premiers.

• Ou si le sous-ensemble ne contient que deux nombres, leur somme est un nombre premier.

Exemple

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

Sortie

3
1 1 2

La description du code ci-dessus

• Nous vérifions d'abord le numéro dans le tableau.

• Si supérieur à 0, parcourez le tableau et vérifiez si chaque élément sauf 1 est nums[i] + 1 est un nombre premier si c'est le cas, imprimez le nombre total de (uns + 1) comme taille du sous-ensemble et le nombre avec cela. Les nombres sont tous des 1.

• Si le tableau donné n'en contient que 1, imprimez-les tous car la somme de toutes les paires sera 2 (nombre premier).

• Si personne n'est présent, vérifiez que la somme de chaque paire du tableau est première.

• Sinon, imprimez -1.

Conclusion

Dans ce tutoriel, nous avons discuté d'un problème dans lequel nous devons trouver le plus grand sous-ensemble d'un tableau donné où la somme de chaque paire est un nombre premier. Nous avons discuté d'un moyen de résoudre ce problème à l'aide du tamis d'Ératosthène et vérifié le nombre dans le tableau. Nous avons également discuté des programmes C++ pour résoudre ce problème, que nous pouvons implémenter à l'aide de langages de programmation comme C, Java, Python, etc. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!