## 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);
}
```