Count Of Pairs In Given Array Whose GCD Is Not Prime

Harsh Goyal
Last Updated: May 13, 2022

Introduction 

This blog will discuss the approach to count the pairs in a given array whose GCD is not prime. Before jumping on the approach of the problem to get to count the pairs in a given array whose GCD is not prime, let’s first understand what GCD is,

The GCD is defined as the largest number which can divide both the given numbers. Example: The GCD of 5 and 16 is 1 because 1 is the only largest number that can divide both numbers.

In this problem, we need to return the count of all the pairs formed by using the elements from the given array whose GCD is not prime.

Example:

Input:

10

5

16

1

 

Output:

4

Explanation:

The pairs whose GCD is not prime are:

(10, 1), (5, 16), (5, 1), (16, 1)

Approach

This approach considers calculating all the prime numbers upto specified ‘max_size’ using the Sieve of Atkin algorithm, and then iteratively checking the GCD’s of all the possible pairs formed from the elements of the array. If the GCD is not prime, then we need to increment the count and then print that count. 

Steps of algorithm

Step 1. Create a function ‘getResult()’ that will accept three parameters, i.e., one vector of integer ‘input’, the second one is the ‘N’ - the size of the vector ‘input’, and the third one is the ‘res’ variable which will keep the count of all the pairs having non-prime GCD.

Step 2. In the ‘getResult’ function, create a vector of ‘max_size’, and allocate 0 at all the indexes.

Step 3. Call the ‘get_primes’ function, which is used to calculate the prime numbers in the vector ‘primes’. 

Step 4. In the ‘get_primes’ function, calculate all the prime numbers by evaluating the conditions mentioned in the code, and then mark all the multiples of squares as non-prime.

Step 5. As 1 is neither prime nor composite, so assign zero at the ‘1st’ index, and assign 1 as ‘2nd’ and ‘3rd’ index as both are prime numbers.

Step 6. Make an iteration using nested ‘for’ loops using the variable i and j, and calculate GCD of each pair formed by elements at ‘ith’ and ‘jth’ index of ‘input’ vector.

Step 7. If the value at index same as the value GCD value of that pair is zero, which means its a non-prime number, then increment the ‘res’ variable.

Step 8. Return from this function, and print the ‘res’.

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

 

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. 

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.

Was this article helpful ?
0 upvotes