/* File: RelPrime.java - March 2018 */
package l06;

/**
* Counting the number of relatively prime pairs (a,b)
* (greatest common divisor = 1) with 1 <= a,b, <= n (note
* that there are better ways to do this using theory)
*
* Sample usage: java l06.RelPrime 10000
*
* Arguments up to 10000 work reasonably quickly (note that for that input
* we're computing 100 million GCDs).
*
* @author Michael Albert
*
*/

public class RelPrime{

  static int calls = 0;

  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    long count = 0;
    for(int i = 1; i <= n; i++) {
      for(int j = i+1; j <= n; j++) {
        if (gcd(i,j) == 1) count += 2; // Once for (i,j) and one for (j,i)
      }
    }
    count += 1; // For (1,1) which was missed
    System.out.println(count + " out of " + (n*n) + " relatively prime pairs");
    System.out.println("Proportion = " + ((double) count)/(n*n));
    System.out.println("Math says proportion tends to " + 
        (6.0/(Math.PI*Math.PI)));
  }

  public static long gcd(long a, long b) {
    if (a == 0) return b;
    return gcd(b % a, a);
  }


}