I want optimized code for this
Implement the following function:
int CountCoprime(int arr[], int n);static int CountCoprime(int[] arr){}static int CountCoprime(int[] arr){}
The function accepts a positive integer array 'arr' of size n. Implement the function to count and return co-prime pairs present in 'arr'.
Co-prime: Two numbers are co-prime if they do not have any common factor except 1.
Assumption:
All elements of array are unique
Note:
Return -1 if array is null
Return 0 if no such pair found
Answers
// program to find coprime pairs from an array of +ve integers
int euclidHcf (int a , int b);
int CountCoprime (int arr[], int n);
int CountCoprime (int arr[]);
int CountCoprime (int n, int arr[]);
int euclidHcf (int a , int b) {
int tmp;
if (b > a) then { tmp=a; a = b; b = tmp; }
while (b != 0 && a!=1) {
tmp = a % b; a = b; b = tmp;
}
return a; //coprime if a = 1.
}
int CountCoprime (int arr[], int n) {
int cnt=0,i, j ;
if (arr ==NULL) return(-1);
for (i=0; i< n; i++)
for (j=i+1; j<n; j++)
if (euclidHcf(a[i], a[j]) == 1) {
cnt++; printf("Coprime: %d %d\n",a[i], a[j]);
}
printf(“Number of coprime pairs: %d\n”,cnt);
return cnt;
}
int CountCoprime(int[] arr) {
int n = sizeof(arr) / sizeof(int);
return CountCoprime(arr, n);
}
int CountCoprime (int n, int arr[]) {
return CountCoprime (arr, n);
}
Answer:
answer is all ready given