/*
   coprimos.c
   ----------

   Seja n um inteiro positivo.  Seja c_np o numero de pares
   de numeros x, y entre 1 e n tais que mdc(x,y) = 1.
   Sabe-se que a razao 

   c_np / n^2    (isto 'e, c_np / (n * n) )

   tende para 6/pi^2.  Este programa verifica este fato.

 */

#include <stdio.h>
#include <math.h>		/* Contem a definicao de M_PI */

int main()
{
  int n, x, y, n_cp;
  int a, b, r;

  printf("Forneca n: ");
  scanf("%d", &n);

  n_cp = 0;

  for (x = 1; x <= n; x++)
    for (y = 1; y <= n; y++) {
      a = x;
      b = y;
      while (b > 0) {
	r = a % b;
	a = b;
	b = r;
      }
      if (a == 1)
	n_cp++;
    }

  printf("Numero de pares coprimos: %d\n", n_cp);
  printf("Razao: %d/%d = %.16g\n", n_cp, n * n, (double) n_cp / (n * n));
  printf("Razao limite: 6/pi^2 = %.16g\n", 6 / (M_PI * M_PI));
  return 0;
}