/*
 *  ass9.c count relatively primes
 */
#include <stdio.h>
int gcd(int,int);
int countRelPrimeI(int [], int);
int countRelPrimeRI(int [], int, int, int, int);
int countRelPrimeR(int [], int, int, int);
int main()
{
    int n, i;
    
    printf("Enter the number of data: ");
    scanf("%d", &n);
    int data[n];
    printf("\nEnter %d +ve integers: ",n);
    for(i=0; i<n; ++i) scanf("%d", &data[i]);
    printf("\nPair of coPrimes: %d\n", 
            countRelPrimeI(data,n));
    printf("\nPair of coPrimes: %d\n", 
            countRelPrimeRI(data,n,0,1, 0));
    printf("\nPair of coPrimes: %d\n", 
            countRelPrimeR(data,n,0,1));
    
    return 0;
}
int gcd(int s, int l){
    if(s == 0) return l;
    return gcd(l%s, s);
}
int countRelPrimeI(int x[], int n){
    int i, j, count=0;

    for(i=0; i<n-1; ++i)
        for(j=i+1; j<n; ++j) 
            if(gcd(x[i],x[j]) == 1) count++;
     putchar('\n');
    return count;
}

int countRelPrimeRI(int x[], int n, int i, int j, int count){
    if(i == n-1) return count;
    if(j == n) return countRelPrimeRI(x, n, i+1, i+2, count);
    if(gcd(x[i],x[j]) == 1) return countRelPrimeRI(x, n, i, j+1, count + 1);
    return countRelPrimeRI(x, n, i, j+1, count); 
}

int countRelPrimeR(int x[], int n, int i, int j){
    if(i == n-1) return 0;
    if(j == n) return countRelPrimeR(x, n, i+1, i+2); 
    if(gcd(x[i],x[j]) == 1) return 1 + countRelPrimeR(x, n, i, j+1);
    else return countRelPrimeR(x, n, i, j+1);
}