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:
