试除法分解质因数

思路

从小到大枚大于1的约数，每次除尽；

注意如果最后x大于1，那么它也是质因数。

算术基本定理

代码

1
2
3
4
5
6
7
8
9
10
void get_div(int x) {
    for(int i = 2; i * i <= x; ++ i) {
        if(x % i == 0) {
            int a = i,b = 0;
            while(x % i == 0) x /= i, ++ b;
            cout << i << " " << b << endl;
        }
    }
    if(x > 1) cout << x << " " << 1 << endl;
}