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