Écrit en C++, trouvez le nombre de nombres premiers dans un sous-tableau

Dans cet article, nous décrirons la méthode pour trouver le nombre de nombres premiers dans un sous-tableau. Nous avons un tableau arr[] de nombres positifs et q requêtes avec deux entiers représentant notre plage {l, R} et nous devons trouver le nombre de nombres premiers dans la plage donnée. Ci-dessous l'exemple du problème donné -

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}.

Façons de trouver la solution

Dans ce cas, j'ai pensé à deux méthodes -

Force brute

Dans cette méthode, nous pouvons prendre la plage et découvrir Le nombre de nombres premiers qui existent dans cette gamme.

Exemple

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

Sortie

2

Cependant, cette méthode n'est pas très bonne car la complexité globale de cette méthode est O(Q*N*√N), ce qui n'est pas très bonne.

Méthode efficace

Dans cette méthode, nous utiliserons le tamis d'Eratosthène pour créer un tableau booléen qui nous indique si l'élément est premier ou non, puis parcourir la plage donnée et trouver le nombre total de nombres premiers dans le tableau. tableau booléen.

Exemple

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

Sortie

2

Explication du code ci-dessus

Cette méthode est beaucoup plus rapide que la méthode de force brute que nous avons appliquée auparavant car la complexité temporelle est maintenant O(Q*N) c'est-à-dire que la complexité précédente était bien mieux.

Dans cette méthode, nous précalculons les éléments et les marquons comme premiers ou non premiers, cela réduit donc notre complexité. En plus de cela, nous utilisons également le tamis d’Ératosthène, qui nous aidera à trouver plus rapidement les nombres premiers. Dans cette méthode, nous étiquetons tous les nombres comme premiers ou non premiers avec une complexité O(N*log(log(N))) en étiquetant les nombres avec des facteurs premiers.

Conclusion

Dans cet article, nous avons résolu le problème de trouver le nombre de nombres premiers dans un sous-tableau en O(Q*N) à l'aide du tamis d'Eratosthène. Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d’autres langages, tels que C, Java, Python et d’autres langages.

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!