Count Of Pairs In Given Array Whose GCD Is Not Prime

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Function to calculate GCD of two numbers
int gcd(int x , int y)
{
   // If one of the element is zero, then gcd is the other element
   if(y == 0)
   {
       return x;
   }
   return gcd(y, x % y);
}

// Function to get all the prime numbers using Sieve of Atkin algo
void get_primes(vector<int> &primes)
{
  int x = primes.size();
  // Calculate all the prime numbers using following conditions
  for(int i = 1 ; i * i < x ; i++)
  {
      for(int j = 1 ; j * j < x; j++)
      {
          int temp = (4 * i * i) + (j * j);
          if(temp <= x && (temp % 12 == 1 || temp % 12 == 5))
          {
              primes[temp] ^= 1;
          }
          temp = (3 * i * i) + (j * j);
          if(temp <= x && temp % 12 == 7)
          {
              primes[temp] ^= 1;
          }
          temp = (3 * i * i) - (j * j);
          if(i > j && temp <= x && temp % 12 == 11)
          {
              primes[temp] ^= 1;
          }
      }
  }
   // 1 is neither prime nor composite
   primes[1] = 0;
   
   // 2 and 3 both are prime numbers
   primes[2] = 1;
   primes[3] = 1;
   // All multiples of squares are non-prime
   for(int i = 5 ; i * i < x ; i++)
   {
       if(primes[i] == 1)
       {
           for(int j = i * i; j < x ; j += i * i)
           {
               primes[j] = 0;
           }
       }
   }
   return;
}

// Function to get total number of pairs
void getResult(vector<int> input, int n, int &res)
{
   int max_size = 1000005;
   vector<int> primes(max_size, 0);

   // Get all the prime numbers in 'primes' vector
   get_primes(primes);

   // Check for all the possible ordered pairs
   for(int i = 0 ; i < n - 1; i++)
   {
       for(int j = i + 1; j < n ; j++)
       {
           // Prime number indexes are marked as 1 in the 'primes' vector
           if(primes[gcd(input[i], input[j])] == 0)
           {
              res++;
           }
       }
   }
   return;
}

int main()
{
   vector<int> input = {10 ,5 , 16, 1};
   int n = input.size();
   cout << "Input Array:- ";
   for(int i = 0 ; i < n ; i++)
   {
       cout << input[i] << ", ";
   }
   cout << endl;
   int res = 0;
   cout << "The total number of pairs whose GCD is not prime are:- ";

   // Function to get total number of pairs
   getResult(input, n, res);
   cout << res << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Output :
Input Array:- 10, 5, 16, 1, 
The total number of pairs whose GCD is not prime are:- 4

Complexity Analysis

Time Complexity: O((N ^ 2)logN)

Incall to ‘getResult()’, we are calculating all the prime numbers using the sieve of Atkin algorithm, and then we are calculating the GCD while making the pairs using nested loops, which takes ‘logN’ and ‘N^2’ computational time respectively, therefore the overall time complexity is O((N^2)*log N), where ‘N’ is the size of the ‘input’ vector.

Space Complexity: O(N)

As we are using extra space to store all the prime numbers which will be ‘N’ in worst case, therefore, the overall space complexity will be O(N).

FAQs

1. What is the time complexity of the Sieve of Atkin?
   The time complexity of the Sieve of Atkin is O(N / (log log N)).
    
2. What is the extended Euclidean algorithm?
   The extended Euclidean algorithm is used to find the coefficients of a and b elements while calculating the GCD given as: Ax + By = gcd(A, B)
    
3. What are the other methods to find the prime numbers?
   We can use the following algorithms to find the prime numbers

• Sieve of Eratosthenes
• Sieve of Atkin
• Sieve of Sundaram

Key takeaways

In this article, we discussed to count the pairs in given Array whose GCD is not prime, discussed the approach to solve this problem programmatically, the time and space complexities. 

Check out the following problems - 

• Sum Of Two Arrays.
• Merge K Sorted Arrays.
• Intersection Of Two Arrays.

Recommended Readings:

• GCD Euclidean Algorithm

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.