Heim > Backend-Entwicklung > C++ > Hauptteil

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

WBOY
Freigeben: 2023-08-25 14:37:11
nach vorne
772 Leute haben es durchsucht

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.
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Ausgabe

Number of prefix sum prime in given range query: 2
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage