Divisors & Factors

Summary

In this post, I will introduce some common techniques related to divisors and factors. 

Details

Number of Divisors

// O(sqrt(n))
int count_divisors(int n) { 
     int cnt = 0; 
     for (int i = 1; i * i <= n; i++) { 
         if (n % i == 0) { 
             if (n / i == i) { // note this
                 cnt++; 
             }
             else { 
                 cnt += 2; 
             }
         } 
     } 
     return cnt
 }

GCD

// gcd(0, b) = b
// gcd(a, b), b > a <=> gcd(b - a, b) <=> gcd(b % a, a) 

// O(h), h => # digits
int gcd(int a, int b) {
  if (a > b) swap(a,b);
  if (a == 0) return b;
  return gcd(b%a, a);
}