title: Find probability of two randomly picked integers (from n integers) to be relatively prime
body: <p>I came across this problem of finding said probability and my first attempt was to come up with following algorithm: I am counting number of pairs which are relatively prime.</p>
  
  <pre><code>int rel = 0
  int total = n * (n - 1) / 2
  for i in [1, n)
      for j in [i+1, n)
          if gcd(i, j) == 1
              ++rel;
  return rel / total
  </code></pre>
  
  <p>which is <em>O(n^2)</em>.</p>
  
  <p>Here is my attempt to reducing complexity:</p>
  
  <p><strong>Observation (1):</strong> 1 is relatively prime to <code>[2, n]</code> so <code>n - 1</code> pairs are trivial.</p>
  
  <p><strong>Observation (2):</strong> 2 is not relatively prime to even numbers in the range <code>[4, n]</code> so remaining odd numbers are relatively prime to 2, so </p>
  
  <pre><code> #Relatively prime pairs = (n / 2) if n is even 
  
                           = (n / 2 - 1) if n is odd.
  </code></pre>
  
  <p>So my improved algorithm would be:</p>
  
  <pre><code>int total = n * (n - 1) / 2
  int rel = 0
  if (n % 2) // n is odd
      rel = (n - 1) + n / 2 - 1
  else // n is even
      rel = (n - 1) + n / 2
  
  for i in [3, n)
      for j in [i+1, n)
          if gcd(i, j) == 1
              ++rel;
  return rel / total
  </code></pre>
  
  <p>With this approach I could reduce two loops, but worst case time complexity is still <code>O(n^2)</code>.</p>
  
  <p><strong>Question:</strong> My question is can we exploit any mathematical properties other than above to find the desired probability in linear time?</p>
  
  <p>Thanks.</p>