约数

求一个数的所有约数 试除法

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> get_divisors(int n){
    vector<int> v;
    for (int i = 1; i <= n / i; i ++ )
        if (n % i == 0) {
            v.push_back(i);
            if (i != n / i) v.push_back(n / i);
        }
    sort(v.begin(), v.end());
    return v;
}

约数个数

设一个数n它有k个约数，a为约数的指数，p为约数
则，约数个数为：
（a1+1)(a2+1)…*(ak+1)

约数之和

(p1^0+p1^1+...+p1^a1)*...*(pk^0+pk^1+...+pk^ak)

最大公约数 欧几里得算法

int gcd(int a, int b){
	return b ? gcd(b, a % b) : a;
}