分解质因数的方法有两种：遍历法和枚举质数法，遍历法的时间复杂度是 O(n)O(\sqrt n)；枚举质数法的时间复杂度是 O(nln⁡n)O(\dfrac{\sqrt n}{\ln \sqrt n})，但是有一个 O(n)O(n) 的预处理。

注意事项：无。

遍历法

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cntpc, p[MAXlog2_x + 10], c[MAXlog2_x + 10];
void evapc(int x) {
    cntpc = 0;
    int sqrtx = sqrt(x);
    for (int i = 2; i <= sqrtx; ++i) {
        if (x % i == 0) {
            p[++cntpc] = i;
            c[cntpc] = 0;
            while (x % i == 0) {
                ++c[cntpc];
                x /= i;
            }
        }
    }
    if (x > 1) {
        p[++cntpc] = x;
        c[cntpc] = 1;
    }
}

枚举质数法

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bool notpr[MAXx + 10]; int cntpr, pr[MAXx / 10 + 100];
void evapr(int n) {
    notpr[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (notpr[i] == 0) {
            pr[++cntpr] = i;
        }
        for (int j = 1, toppj = n / i; j <= cntpr && pr[j] <= toppj; ++j) {
            notpr[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}

int cntpc, p[MAXlog2_x + 10], c[MAXlog2_x + 10];
void evapc(int x) {
    cntpc = 0;
    int sqrtx = sqrt(x);
    for (int i = 1; i <= cntpr && pr[i] <= sqrtx; ++i) {
        if (x % pr[i] == 0) {
            p[++cntpc] = pr[i];
            c[cntpc] = 0;
            while (x % pr[i] == 0) {
                ++c[cntpc];
                x /= pr[i];
            }
        }	
    }
    if (x > 1) {
        p[++cntpc] = x;
        c[cntpc] = 1;
    }
}

evapr(MAXx);
evapc(x1); evapc(x2); // ...