试除法
时间复杂度O($\sqrt x$), x 是数的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
signed main() {
    int x;    // 对 x 进行质因数分解
    cin >> x;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            int cnt = 0;
            while(x % i == 0) {
                x /= i;
                cnt++;
            }
            cout << i << " " << cnt << endl;
        }
    }
    if (x > 1) cout << x << " " << 1 << endl;
}

筛法，对 n 个数进行质因数分解
时间复杂度O(Nlog(X))，N是数的个数，X是数的范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main(){
    cin >> n;
    get_primes(n); // 埃氏筛或线性筛，处理出每个数的最小值质因数
    for (int i = 1; i <= n; i++) {
        int x, last = -1, cnt = 0;
        cin >> x;
        while(x != 1) { // v[x] 是处理出来的x的最小质因数
            if (v[x] != last) {
                if (last != -1) 
                    cout << last << " " << cnt << endl;
                cnt = 0;
                last = v[x];
            }
            cnt++;
            x /= v[x];
        }
        cout << last << " " << cnt << endl;
    }
}