C++ Maximale Teilmenge, bei der die Summe jedes Elementpaars eine Primzahl ist

Finden Sie die größte Teilmenge aus dem angegebenen Array, wobei die Summe jedes Elementpaars eine Primzahl ist. Angenommen, das maximale Element ist 100000, zum Beispiel −

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.

Möglichkeiten, die Lösung zu finden

Um festzustellen, ob das Zahlenpaar Primzahlen ist, müssen wir zunächst prüfen, ob ihre Summe ungerade oder gerade ist, da gerade Zahlen keine Primzahlen sind außer 2. Wenn beide Zahlen ungerade oder gerade sind, kann ihre Summe außerdem gerade sein.

In diesem Problem nehmen wir drei Zahlen, x, y und z, zwei davon sollten ungerade oder gerade sein. Wir werden dann prüfen, ob diese Teilmenge Paare von Primsummen enthält, was möglich sein kann, wenn:

• Die Teilmenge enthält einige Zahlen von 1 und einige andere Zahlen, bei denen NUM + 1 Primzahlen sein sollten.

• Oder wenn die Teilmenge nur zwei Zahlen enthält, ist ihre Summe eine Primzahl.

Beispiel

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

Ausgabe

3
1 1 2

Die obige Codebeschreibung

• Zuerst überprüfen wir die Zahl im Array.

• Wenn größer als 0, iterieren Sie über das Array und prüfen Sie, ob jedes Element außer 1 eine Primzahl ist. Wenn ja, geben Sie die Gesamtzahl von (Einsen + 1) als Größe aus Teilmenge und die Zahl mit dieser Zahl sind alle Einsen.

• Wenn das angegebene Array nur 1 enthält, drucken Sie alle aus, da die Summe aller Paare 2 (Primzahl) beträgt.

• Wenn niemand anwesend ist, überprüfen Sie, ob die Summe jedes Paares im Array eine Primzahl ist.

• Else print -1.

Fazit

In diesem Tutorial haben wir ein Problem besprochen, bei dem wir die größte Teilmenge aus einem gegebenen Array finden müssen, bei dem die Summe jedes Paares eine Primzahl ist. Wir haben eine Möglichkeit besprochen, dieses Problem mit Hilfe des Siebes des Eratosthenes zu lösen und die Zahl im Array zu überprüfen. Wir haben auch C++-Programme zur Lösung dieses Problems besprochen, die wir mithilfe von Programmiersprachen wie C, Java, Python usw. implementieren können. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

Das obige ist der detaillierte Inhalt vonC++ Maximale Teilmenge, bei der die Summe jedes Elementpaars eine Primzahl ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!