Écrit en C++, trouvez le nombre de préfixes et de nombres premiers dans une plage donnée

Dans cet article, nous devons trouver plusieurs sommes de préfixes premiers dans le tableau d'entiers positifs donné arr[ ] et effectuer des requêtes de plage L, R , où L est le tableau prefixsum[ ] L'index initial valeur arr[L], R est le nombre de sommes de préfixes que nous devons trouver.

Pour remplir le tableau de somme de préfixes, nous commençons de l'index L à l'index R et ajoutons la valeur actuelle avec le dernier élément du tableau donné. Voici l'exemple du problème -

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.

Façon de trouver la solution

À partir de ce problème, nous pouvons dire que nous devons créer un nouveau tableau prefixsum[ ] et ajouter la somme des préfixes en ajoutant l'élément précédent du tableau et l'élément actuel élément de l’élément de tableau donné. Le premier élément du tableau de somme de préfixes sera la valeur à l'index L dans le tableau donné.

Nous devons exécuter une boucle de L à R, où L et R sont les tableaux donnés, puis vérifier les éléments du tableau prefixsum[ ] et incrémenter le nombre pour chaque nombre premier trouvé.

Exemple

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

Output

Number of prefix sum prime in given range query: 2

Explication du code ci-dessus

Dans ce code, nous créons un tableau prefixsum[ ] et le remplissons avec la somme de l'élément précédent du tableau prefixsum[ ] et de l'élément actuel du tableau donné. Après cela, nous vérifions si tous les nombres du tableau de préfixes sont premiers ou non. Nous utilisons ici l'algorithme Sieve d'Eratosthène pour vérifier les nombres premiers. Enfin, augmentez le nombre pour chaque nombre premier et affichez le résultat.

Conclusion

Dans cet article, nous avons trouvé des nombres premiers dans des tableaux de sommes de préfixes en appliquant une approche naïve et en utilisant Sieve of Eratosthenes. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!