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

Dans cet article, nous expliquerons tout sur la recherche du nombre de paires premières dans un tableau en utilisant C++. Nous avons un tableau d'entiers arr[] et nous devons trouver toutes les paires possibles de nombres premiers qui y sont présentes. Voici un exemple du problème -

Input : arr[ ] = { 1, 2, 3, 5, 7, 9 }

Output : 6

From the given array, prime pairs are
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)

Input : arr[] = {1, 4, 5, 9, 11}

Output : 1

Façons de trouver une solution

Méthode par force brute

Nous allons maintenant discuter de la méthode la plus basique, c'est-à-dire la méthode par force brute et essayer de trouver une autre méthode : Cette méthode n'est pas efficace.

Exemple

#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
    bool p[MAX+1];
    memset(p, true, sizeof(p));
    p[1] = false;
    p[0] = false;
     for(int i = 2; i * i <= MAX; i++){
        if(p[i] == true){
            for(int j = i*2; j <= MAX; j += i){
               p[j] = false;
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(p[arr[i]] == true)
           prime[i] = true;
    }
}
int main(){
    int arr[] = {1, 2, 3, 5, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
    int answer = 0; // counter variable to count the number of prime pairs.
    int MAX = INT_MIN; // Max element
    for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
    }
    bool prime[n]; // boolean array that tells if the element is prime or not.
    memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
    seiveOfEratosthenes(arr, prime, n, MAX);
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            if(prime[i] == true && prime[j] == true)
               answer++;
         }
    }
    cout << answer << "\n";
    return 0;
}

Sortie

6

Dans cette approche, nous créons un tableau booléen qui nous indique si chaque élément est premier ou non, puis nous parcourons toutes les paires possibles et vérifions les deux nombres dans la paire s'il s'agit d'un nombre premier. . S'il s'agit d'un nombre premier, augmentez la réponse de un et continuez.

Mais cette méthode n'est pas très efficace car sa complexité temporelle est O(N*N), où N est la taille du tableau, nous voulons donc maintenant rendre cette méthode plus rapide.

Méthode efficace

Dans cette méthode, la majeure partie du code est la même, mais le changement clé est qu'au lieu de parcourir toutes les paires possibles, nous utilisons une formule pour les calculer.

Exemple

#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
   bool p[MAX+1];
   memset(p, true, sizeof(p));
   p[1] = false;
   p[0] = false;
   for(int i = 2; i * i <= MAX; i++){
       if(p[i] == true){
           for(int j = i*2; j <= MAX; j += i){
               p[j] = false;
           }
       }
    }
    for(int i = 0; i < n; i++){
       if(p[arr[i]] == true)
           prime[i] = true;
   }
}
int main(){
   int arr[] = {1, 2, 3, 5, 7, 8, 9};
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
   int answer = 0; // counter variable to count the number of prime pairs.
   int MAX = INT_MIN; // Max element
   for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
   }
   bool prime[n]; // boolean array that tells if the element is prime or not.
   memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
   seiveOfEratosthenes(arr, prime, n, MAX);
   for(int i = 0; i < n; i++){
       if(prime[i] == true)
           answer++;
   }
   answer = (answer * (answer - 1)) / 2;
   cout << answer << "\n";
   return 0;
}

Sortie

6

Comme vous pouvez le voir, la majeure partie du code est la même que la méthode précédente, mais le changement clé qui réduit considérablement la complexité est la formule que nous utilisons, qui est n(n-1) /2 , qui comptera notre nombre de paires premières.

Explication du code ci-dessus

Dans ce code, nous utilisons le tamis d'Eratosthène pour étiqueter tous les nombres premiers jusqu'à ce que nous soyons dans un gros lot. Dans un autre tableau booléen, nous marquons par index si l'élément est premier ou non.

Enfin, nous parcourons l'ensemble du tableau, trouvons le nombre total de nombres premiers présents et trouvons toutes les paires de nombres premiers possibles en utilisant la formule n*(n-1)/2. Avec cette formule, notre complexité est réduite à O(N), où N est la taille du tableau.

Conclusion

Dans cet article, nous avons résolu un problème pour trouver le nombre de paires premières présentes dans un tableau en complexité temporelle O(n). 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!