title: efficient way to find gcd pairs for an upper bound number, 10000 in java
body: <p>I want to find pairs  having GCD=1 upto a certain number, say 10000.
  I am using 2 nested loops and calling a method with long parameters.
  but code is running damn slow, any efficient approach is required.
  Thanks</p>
  
  <pre><code>class FastGCD {
  
      public static long GCD(long a, long b) {
  
          return (b == 0 ? a : GCD(b, a % b));
      }
  
      public static void main(String ah[]) throws Exception{
  
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int cases = 0;
  
          long number = 0, output = 0;
          try {
              cases = Integer.parseInt(br.readLine());
  
          } catch (NumberFormatException e) {
              System.exit(0);
          } catch (IOException e) {
              System.exit(0);
          }
          for (int i = 1; i &lt;= cases; i++) {
              try {
                  number = Long.parseLong(br.readLine());
                  } catch (NumberFormatException e) {
                  e.printStackTrace();
                  System.exit(0);
              } catch (IOException e) {
                  e.printStackTrace();
                  System.exit(0);
              }
              for (int j = 0; j &lt; number; j++) {
                  for (int k = 0; k &lt; number; k++) {
  
                      if (FastGCD.GCD(j, k) == 1)
                          {
                          //System.out.println("here"+j+","+k);
                          output++;
                      }
                  }
              }
              System.out.println(output);
          }
      }
  }
  </code></pre>