title: How many numbers below N are coprimes to N?
body: <h2>In short:</h2>
  
  <p>Given that <strong>a</strong> is coprime to <strong>b</strong> if <strong>GCD(a,b) = 1</strong> (where GCD stands for <a href="http://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noreferrer">great common divisor</a>), how many positive integers below N are coprime to N?</p>
  
  <p>Is there a clever way?</p>
  
  <hr>
  
  <h2>Not necessary stuff</h2>
  
  <p>Here is the dumbest way:</p>
  
  <pre><code>def count_coprime(N):
      counter = 0
      for n in xrange(1,N):
          if gcd(n,N) == 1:
              counter += 1
      return counter
  </code></pre>
  
  <p>It works, but it is slow, and dumb. I'd like to use a clever and faster algorithm.
  I tried to use prime factors and divisors of N but I always get something that doesn't work with larger N.</p>
  
  <p><s>I think the algorithm should be able to count them without calculating all of them like the dumbest algorithm does :P</s></p>
  
  <h2>Edit</h2>
  
  <p>It seems I've found a working one:</p>
  
  <pre><code>def a_bit_more_clever_counter(N):
      result = N - 1
      factors = []
      for factor, multiplicity in factorGenerator(N):
          result -= N/factor - 1
          for pf in factors:
              if lcm(pf, factor) &lt; N:
                  result += N/lcm(pf, factor) - 1
          factors += [factor]
      return result
  </code></pre>
  
  <p>where lcm is least common multiple. Does anyone have a better one?</p>
  
  <h2>Note</h2>
  
  <p>I'm using python, I think code should be readable even to who doesn't know python, if you find anything that is not clear just ask in the comments. I'm interested in the algorithm and the math, the idea. </p>