Q412: Pi

/*
 Run time: 0.310
 判斷互質與否，可以直接用輾轉相除法找 gcd
 如果 gcd is one 表示互質
 這樣做會比用for loop 一個一個找有效率很多
*/
#include <stdio.h>
#include <math.h>
bool test(int a, int b);
void swap(int &a, int &b);
int gcd(int a, int b);
int total;

int main()
{
 int n;
 int i, j;
 int count;
 double PI;
 while (scanf("%d", &n))
 {
     if (!n) break;

     total = 0;
     count = 0;
     int *arr = new int[n];

     for ( i = 0; i < n; i++)
         scanf("%d", &arr[i]);

     for ( i = 0; i < n; i++)
         for ( j = i+1; j < n; j++)
             if (test(arr[i], arr[j]))
                 count++;

     if (!count) printf("No estimate for this data set.\n");
     else
     {
         PI = sqrt(6.0*total/count);
         printf("%.6lf\n", PI);
     }

 }

}

bool test(int a, int b)
{
 total++;
 int i;
 if (a == b) return false;

 if (a > b)  swap(a, b);

 if (gcd(a, b) == 1)
     return true;
 else
     return false;
}

void swap(int &a, int &b)
{
 int tmp;
 tmp = a;
 a = b;
 b = tmp;
}

int gcd(int a, int b)
{
 if (!a)
     return b;
 else
     return gcd(b%a, a);

}