Program: Count the number of co-prime pairs in an array. (co-prime numbers means Any two numbers whose GCD is 1)

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

Output: Count the number of co-prime pairs in an array.

Sample Input and Output:

Input 1:

3

1 2 3

Output 1:

3

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

Input 2:

4

4 8 3 9

Output 2:

4

Here, Co-prime pairs are (4, 3), (8, 3), (4, 9 ), (8, 9 )

Code in C:

#include<stdio.h>
int coprime(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 (coprime(arr[i], arr[j]))
   count++;
       }     
}
return count;
}

int main()
{
int n;
scanf("%d", &n);
int a[25], i;
for(i=0; i<n; i++)
scanf("%d", &a[i]);
printf("%d", count_pairs(a, n));
return 0;
}
Code in Java:
import java.util.*; 

class Co_prime
{

static int coprime(int a, int b)
{ 
int gcd=0;
while ( a != 0 )
{
gcd = a; 
a = b%a; 
b = gcd;
}
if(gcd == 1)
return 1;
else
return 0;
}

static 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 (coprime(arr[i], arr[j])==1)
   count++;
       }     
}
return count;
}

public static void main(String args[])
{
int num1;
Scanner sc = new Scanner(System.in);  
num1 = sc.nextInt();
int a[]=new int[25];
for(int i=0; i<num1; i++)
  a[i] = sc.nextInt();
System.out.println(count_pairs(a, num1));

}
}
OutPut:
Coprime numbers

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top