Written in C++, find the number of pairs of prime numbers in an array

In this article, we will explain everything about finding the number of pairs of prime numbers in an array using C. We have an array of integers arr[] and we need to find all possible pairs of prime numbers present in it. Here is an example of the problem -

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

Methods to find solution

Brute force method

Now we will discuss the most basic method i.e. brute force method and try to find another This method: This method is not efficient.

Example

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

Output

6

In this approach we create a boolean array that tells us whether each element is prime or not, then we iterate over all Possible pairings and check if the two numbers in the pairing are prime. If it is a prime number, increase the answer by one and continue.

But this method is not very efficient because its time complexity is O(N*N), where N is the size of the array, so now we have to use this method Faster.

Efficient method

In this method, most of the code is the same, but the key change is that instead of looping through all possible pairings, we use a formula to calculate they.

Example

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

Output

6

As you can see, most of the code is the same as the previous method, but the key change that greatly reduces the complexity is that we use The formula for , i.e. n(n-1)/2, will calculate the number of pairs of prime numbers we have.

Explanation of the above code

In this code, we use the sieve of Eratosthenes to label all prime numbers until we are in a large batch. In another boolean array, we mark by index whether the element is prime or not.

Finally, we loop through the entire array, find the total number of primes present, and find all possible pairs of primes using the formula n*(n-1)/2. With this formula, our complexity is reduced to O(N), where N is the size of the array.

Conclusion

In this article, we solved a problem to find the number of prime pairs present in an array with O(n) time complexity. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages, such as C, java, python and other languages.

The above is the detailed content of Written in C++, find the number of pairs of prime numbers in an array. For more information, please follow other related articles on the PHP Chinese website!