Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
2.1.
Steps of algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key takeaways
Last Updated: Mar 27, 2024

# Count Of Pairs In Given Array Whose GCD Is Not Prime

Harsh Goyal
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## 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:

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’.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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.

Check out the following problems -

Recommended Readings:

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.

Live masterclass