In C++ geschrieben: Finden Sie die Anzahl der Primzahlpaare in einem Array

In diesem Artikel erklären wir alles über das Ermitteln der Anzahl von Primzahlpaaren in einem Array mit C++. Wir haben ein Array von ganzen Zahlen arr[] und müssen alle darin vorhandenen möglichen Primzahlpaare finden. Hier ist ein Beispiel für das Problem –

Input : arr[ ] = { 1, 2, 3, 5, 7, 9 }

Output : 6

From the given array, prime pairs are
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)

Input : arr[] = {1, 4, 5, 9, 11}

Output : 1

Möglichkeiten, eine Lösung zu finden

Brute-Force-Methode

Jetzt besprechen wir die grundlegendste Methode, d. h. die Brute-Force-Methode, und versuchen, einen anderen Weg zu finden: Diese Methode ist nicht effizient.

Beispiel

#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
    bool p[MAX+1];
    memset(p, true, sizeof(p));
    p[1] = false;
    p[0] = false;
     for(int i = 2; i * i <= MAX; i++){
        if(p[i] == true){
            for(int j = i*2; j <= MAX; j += i){
               p[j] = false;
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(p[arr[i]] == true)
           prime[i] = true;
    }
}
int main(){
    int arr[] = {1, 2, 3, 5, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
    int answer = 0; // counter variable to count the number of prime pairs.
    int MAX = INT_MIN; // Max element
    for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
    }
    bool prime[n]; // boolean array that tells if the element is prime or not.
    memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
    seiveOfEratosthenes(arr, prime, n, MAX);
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            if(prime[i] == true && prime[j] == true)
               answer++;
         }
    }
    cout << answer << "\n";
    return 0;
}

Ausgabe

6

Bei diesem Ansatz erstellen wir ein boolesches Array, das uns sagt, ob jedes Element eine Primzahl ist oder nicht, dann durchlaufen wir alle möglichen Paarungen und überprüfen beide Zahlen in der Paarung, ob es eine Primzahl ist . Wenn es sich um eine Primzahl handelt, erhöhen Sie die Antwort um eins und fahren Sie fort.

Aber diese Methode ist nicht sehr effizient, da ihre zeitliche Komplexität O(N*N) beträgt, wobei N die Größe des Arrays ist, also wollen wir diese Methode jetzt schneller machen.

Effiziente Methode

Bei dieser Methode ist der größte Teil des Codes derselbe, aber die entscheidende Änderung besteht darin, dass wir nicht alle möglichen Paarungen durchlaufen, sondern eine Formel verwenden, um sie zu berechnen.

Beispiel

#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
   bool p[MAX+1];
   memset(p, true, sizeof(p));
   p[1] = false;
   p[0] = false;
   for(int i = 2; i * i <= MAX; i++){
       if(p[i] == true){
           for(int j = i*2; j <= MAX; j += i){
               p[j] = false;
           }
       }
    }
    for(int i = 0; i < n; i++){
       if(p[arr[i]] == true)
           prime[i] = true;
   }
}
int main(){
   int arr[] = {1, 2, 3, 5, 7, 8, 9};
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
   int answer = 0; // counter variable to count the number of prime pairs.
   int MAX = INT_MIN; // Max element
   for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
   }
   bool prime[n]; // boolean array that tells if the element is prime or not.
   memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
   seiveOfEratosthenes(arr, prime, n, MAX);
   for(int i = 0; i < n; i++){
       if(prime[i] == true)
           answer++;
   }
   answer = (answer * (answer - 1)) / 2;
   cout << answer << "\n";
   return 0;
}

Ausgabe

6

Wie Sie sehen können, ist der größte Teil des Codes derselbe wie bei der vorherigen Methode, aber die wichtigste Änderung, die die Komplexität erheblich reduziert, ist die von uns verwendete Formel, die n(n-1) ist. /2 , wodurch die Anzahl unserer Primzahlpaare gezählt wird.

Erklärung des obigen Codes

In diesem Code verwenden wir das Sieb des Eratosthenes, um alle Primzahlen zu kennzeichnen, bis wir eine große Menge haben. In einem anderen booleschen Array markieren wir anhand des Index, ob das Element eine Primzahl ist oder nicht.

Abschließend durchlaufen wir das gesamte Array, ermitteln die Gesamtzahl der vorhandenen Primzahlen und ermitteln alle möglichen Primzahlpaare mithilfe der Formel n*(n-1)/2. Mit dieser Formel wird unsere Komplexität auf O(N) reduziert, wobei N die Größe des Arrays ist.

Fazit

In diesem Artikel haben wir ein Problem gelöst, um die Anzahl der in einem Array vorhandenen Primzahlpaare in O(n)-Zeitkomplexität zu ermitteln. Wir haben auch ein C++-Programm zur Lösung dieses Problems und einen vollständigen Weg zur Lösung dieses Problems (normal und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben.

Das obige ist der detaillierte Inhalt vonIn C++ geschrieben: Finden Sie die Anzahl der Primzahlpaare in einem Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!