Search

# Cocubes Coding | Co-prime pairs in array

In this blog we are discussing a cocubes coding question to count the number of co-prime pairs in an array.

Now by co-prime we mean that any two numbers whose GCD is 1 are be called as co-prime.

Input:

The first line contains an integer T, total number of elements. Then follow T elements.

```3
1 2 3```

Output:

Count the number of co-prime pairs in an array

`3`

Here, Co-prime pairs are (1, 2), (2, 3), (1, 3)

Constraints:

```1 <= T <= 25
1 <= elements <= 100```

Implementation using C:

```#include <stdio.h>
int co_prime(int a, int b)
{
int gcd;
while( a!=0 )
{   gcd = a;
a = b%a;
b = gcd;
}
if(gcd == 1)
return 1;
else
return 0;
}

int count_pairs(int arr[], int n)
{
int count = 0;
for(int i = 0; i < n-1; i++)
{
for(int j = i + 1; j < n; j++)
{
if(co_prime(arr[i], arr[j]))
count++;
}
}
return count;
}

int main()
{
int n;
scanf("%d", &n);

int a, i;
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("%d", count_pairs(a, n));

return 0;
}```

Happy Coding!

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem.

49 views1 comment

See All