In C++ geschrieben, ermitteln Sie die Anzahl der Primzahlen in einem Subarray

In diesem Artikel beschreiben wir die Methode, um die Anzahl der Primzahlen in einem Subarray zu ermitteln. Wir haben ein Array arr[] aus positiven Zahlen und q Abfragen mit zwei ganzen Zahlen, die unseren Bereich {l, R} darstellen, und wir müssen die Anzahl der Primzahlen in dem angegebenen Bereich ermitteln. Unten ist ein Beispiel für das gegebene Problem –

Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3

Output : 2

In the given range the primes are {2, 3}.

Input : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5

Output : 4

In the given range the primes are {2, 3, 5, 11}.

Möglichkeiten, die Lösung zu finden

In diesem Fall habe ich an zwei Methoden gedacht –

Brute Force

Bei dieser Methode können wir den Bereich nehmen und die Anzahl der Primzahlen herausfinden Zahlen, die in diesem Bereich existieren.

Beispiel

#include <bits/stdc++.h>
using namespace std;
bool isPrime(int N){
    if (N <= 1)
       return false;
    if (N <= 3)
       return true;
    if(N % 2 == 0 || N % 3 == 0)
       return false;
    for (int i = 5; i * i <= N; i = i + 2){ // as even number can&#39;t be prime so we increment i by 2.
       if (N % i == 0)
           return false; // if N is divisible by any number then it is not prime.
    }
    return true;
}
int main(){
    int N = 6; // size of array.
    int arr[N] = {1, 2, 3, 4, 5, 6};
    int Q = 1;
    while(Q--){
        int L = 0, R = 3;
        int cnt = 0;
        for(int i = L; i <= R; i++){
           if(isPrime(arr[i]))
               cnt++; // counter variable.
        }
        cout << cnt << "\n";
    }
    return 0;
}

Ausgabe

2

Diese Methode ist jedoch nicht sehr gut, da die Gesamtkomplexität dieser Methode O(Q*N*√N) beträgt, was nicht sehr gut ist.

Effiziente Methode

In dieser Methode verwenden wir Sieve of Eratosthenes, um ein boolesches Array zu erstellen, das uns sagt, ob das Element eine Primzahl ist oder nicht, und dann durch den angegebenen Bereich iterieren und die Gesamtzahl der Primzahlen im Array ermitteln . boolesches Array.

Beispiel

#include <bits/stdc++.h>
using namespace std;
vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){
    vector<bool> p(n);
    bool Prime[MAX + 1];
    for(int i = 2; i < MAX; i++)
       Prime[i] = true;
    Prime[1] = false;
    for (int p = 2; p * p <= MAX; p++) {
       // If prime[p] is not changed, then
       // it is a prime
       if (Prime[p] == true) {
           // Update all multiples of p
           for (int i = p * 2; i <= MAX; i += p)
               Prime[i] = false;
       }
    }
    for(int i = 0; i < n; i++){
        if(Prime[arr[i]])
           p[i] = true;
        else
           p[i] = false;
    }
    return p;
}
int main(){
    int n = 6;
    int arr[n] = {1, 2, 3, 4, 5, 6};
    int MAX = -1;
    for(int i = 0; i < n; i++){
        MAX = max(MAX, arr[i]);
    }
    vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // boolean array.
    int q = 1;
    while(q--){
        int L = 0, R = 3;
        int cnt = 0; // count
        for(int i = L; i <= R; i++){
            if(isprime[i])
               cnt++;
       }
       cout << cnt << "\n";
   }
   return 0;
}

Ausgabe

2

Erklärung des obigen Codes

Diese Methode ist viel schneller als die Brute-Force-Methode, die wir zuvor angewendet haben, da die Zeitkomplexität jetzt O(Q*N) beträgt, d. h. als die vorherige Komplexität viel besser.

Bei dieser Methode berechnen wir die Elemente vorab und markieren sie als Primzahl oder Nicht-Primzahl, wodurch unsere Komplexität verringert wird. Darüber hinaus verwenden wir auch das Sieb des Eratosthenes, das uns dabei helfen wird, Primzahlen schneller zu finden. Bei dieser Methode kennzeichnen wir alle Zahlen als Primzahlen oder Nicht-Primzahlen mit der Komplexität O(N*log(log(N))), indem wir die Zahlen mit Primfaktoren kennzeichnen.

Fazit

In diesem Artikel haben wir das Problem gelöst, die Anzahl der Primzahlen in einem Subarray in O(Q*N) mithilfe von Sieve of Eratosthenes 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, ermitteln Sie die Anzahl der Primzahlen in einem Subarray. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!