title: Complexity of prime factor algorithm
body: <p>I just studied how to find the prime factors of a number with <a href="http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/" rel="nofollow">this</a> algorithm that basically works this way:</p>
  
  <pre><code>void printPrimeFactors(N) {
  
    while N is even
      print 2 as prime factor
      N = N/2
  
    // At this point N is odd
    for all the ODDS i from 3 to sqrt(N)
      while N is divisible by i
        print i as prime factor
        N = N / i
  
    if N hasn't been divided by anything (i.e. it's still N)
      N is prime
  
    }
  </code></pre>
  
  <p>everything is clear but <strong>I'm not sure how to calculate the complexity in big-O of the program above</strong>.</p>
  
  <p>Being the division the most expensive operation (I suppose), I'd say that as a worst-case there could be a maximum of log(N) divisions, but I'm not totally sure of this.</p>