In C++ geschrieben, ermitteln Sie die Anzahl der Präfix- und Primzahlen in einem bestimmten Bereich

In diesem Artikel müssen wir mehrere Primpräfixsummen im gegebenen positiven Ganzzahlarray arr[ ] finden und Bereichsabfragen L, R durchführen, wobei L das Präfixsum[ ]-Array ist. Der Anfangsindex value arr[L], R ist die Anzahl der Präfixsummen, die wir finden müssen.

Um das Präfix-Summen-Array zu füllen, beginnen wir mit Index L bis Index R und addieren den aktuellen Wert mit dem letzten Element im angegebenen Array. Hier ist das Beispiel des Problems –

Input : arr[ ] = { 3, 5, 6, 2, 4 }
L = 1, R = 3
Output : 3
Explanation : prefixsum[ 0 ] = arr[ L ] = 5
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 2 ] = 11
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 3 ] = 13
In prefixsum[ ] array all three 5, 11 and 13 are prime numbers in prefix sum array in given range.

Input : arr[ ] = { 6, 10, 5, 8, 11 }
L = 0, R = 3
Output : 1
Explanation : prefixsum[ 0 ] = arr[ L ] = 6
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 1 ] = 16
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 2 ] = 21
prefixsum[ 3 ] = prefixsum[ 2 ] + arr[ 3 ] = 29
In prefixsum[ ] array only 29 is the prime number in prefix sum array given range.

Weg, die Lösung zu finden

Ausgehend von diesem Problem können wir sagen, dass wir ein neues Array prefixsum[ ] erstellen und das Präfix sum hinzufügen müssen, indem wir das vorherige Element des Arrays und das aktuelle hinzufügen Element des angegebenen Array-Elements. Das erste Element des Präfix-Summen-Arrays ist der Wert am Index L im angegebenen Array.

Wir müssen eine Schleife von L nach R ausführen, wobei L und R die angegebenen Arrays sind, und dann die Elemente des Arrays prefixsum[ ] überprüfen und die Anzahl für jede gefundene Primzahl erhöhen.

Beispiel

#include<bits/stdc++.h>
using namespace std;
vector < bool > checkprime (int *arr, int n, int MAX){
    vector < bool > p (n);
    bool Prime_val[MAX + 1];
    for (int i = 2; i < MAX; i++)
        Prime_val[i] = true;
        Prime_val[1] = false;
    for (int p = 2; p * p <= MAX; p++){
        // If prime[p] is not changed, then
        // it is a prime
        if (Prime_val[p] == true){
            // Update all multiples of p
            for (int i = p * 2; i <= MAX; i += p)
                Prime_val[i] = false;
        }
    }
    for (int i = 0; i < n; i++){
        if (Prime_val[arr[i]])
             p[i] = true;
        else
        p[i] = false;
    }
    return p;
}
int main (){
    int arr[] = { 2, 3, 4, 7, 9, 10 };
    int s1 = sizeof (arr) / sizeof (arr[0]);//size of given array
    int L = 1, R = 3, s2 = R - L + 1;
    int prefixsum[s2];
    int count = 0;
    prefixsum[0] = arr[L];
    for (int i = L + 1, j = 1; i <= R && j < s1; i++, j++){
        prefixsum[j] = prefixsum[j - 1] + arr[i];

    }
    vector < bool > isprime = checkprime (prefixsum, s2, prefixsum[s2 - 1]);
    for (int i = 0; i < s2; i++) {
        if (isprime[i] == 1)
            count++;
    }
    cout <<"Number of prefix sum prime in given range query: " << count;
    return 0;
}

Ausgabe

Number of prefix sum prime in given range query: 2

Erklärung des obigen Codes

In diesem Code erstellen wir ein Array prefixsum[ ] und füllen es mit der Summe des vorherigen Elements des Arrays prefixsum[ ] und dem aktuellen Element des gegebenes Array. Danach prüfen wir, ob alle Zahlen des Präfixarrays Primzahlen sind oder nicht. Hier verwenden wir den Sieve of Eratosthenes-Algorithmus, um nach Primzahlen zu suchen. Erhöhen Sie abschließend die Anzahl für jede Primzahl und zeigen Sie das Ergebnis an.

Fazit

In diesem Artikel haben wir Primzahlen in Präfixsummen-Arrays gefunden, indem wir einen naiven Ansatz angewendet und das Sieb des Eratosthenes verwendet haben. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonIn C++ geschrieben, ermitteln Sie die Anzahl der Präfix- und Primzahlen in einem bestimmten Bereich. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!