Maison > développement back-end > C++ > Écrit en C++, trouvez le nombre de paires de nombres premiers dans un tableau

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

王林
Libérer: 2023-09-15 10:57:02
avant
1123 Les gens l'ont consulté

É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
Copier après la connexion

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;
}
Copier après la connexion

Sortie

6
Copier après la connexion
Copier après la connexion

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;
}
Copier après la connexion

Sortie

6
Copier après la connexion
Copier après la connexion

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!

Étiquettes associées:
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal