快速求出某数的所有约数

故事是这样的，有一场比赛题，本来应该是考察 DP 的，但是算法写出来之后，一值暴 TLE，我一开始以为是 C++ 的 map 是 log(n) 的复杂度，于是改成了 unorder_map 试了下，结果还是 TLE。最后花了很久定位到求约数的算法超时。

按照人惯性的思维，求一个数的约数，直接使用一个 for 就可以了。而且算法的复杂度是 O(n) 具体一点可以说是 O(sqrt(n)) 也是可以接受的。

但是，还是有另一个更加快速的方法。

using namespace std;
int prime[100000];
bool isPrime[1000005];
void getPrime(int x){
    for (int i = 1; i < x; i += 2) {
        isPrime[i] = 1;
        isPrime[i - 1] = 0;
    }
    prime[prime[0] = 1] = 2;
    for (int i = 3; ;i += 2) {
        if(isPrime[i]) {
            int j = i*i, k = i+i;
            if(j >= x) break;
            while(j < x ) {
                isPrime[j] = 0;  j += k;
            }
        }
    }
    for (int i = 3; i < x; i += 2) {
        if(isPrime[i]) {
            prime[++prime[0]] = i;
        }
    }
}
int p[34380], cnt[34380];
void getPrimeDivisor( int x ) {
    p[0] = cnt[0] = 0; int t;
    for (int i = 1; prime[i]*prime[i] <= x  && i <= prime[0]; ++i) {
        t = 0;
        while (x%prime[i] == 0) {
            ++t; x /= prime[i];
        }
        if (t) {
            p[++p[0]] = prime[i];
            cnt[++cnt[0]] = t;
        }
    }
    if (x > 1) {
        p[++p[0]] = x;
        cnt[++cnt[0]] = 1;
    }
};
vector<int> getDivisor(int x) {
    getPrimeDivisor(x);
    vector<int> divisor(1500);
    divisor[0] = 1;
    divisor[1] = 1;
    for (int i = 1; i <= p[0]; ++i) {
        int nowNum = divisor[0];
        int base = 1;
        for (int j = 1; j <= cnt[i]; ++j) {
            base *= p[i];
            for (int k = 1; k <= divisor[0]; ++k)
                divisor[++nowNum] = divisor[k]*base;
        }
        divisor[0] = nowNum;
    }
    return divisor;
}
int main() {
    getPrime(10000);
    vector<int> res = getDivisor(80);
    for (int i = 1; i <= res[0]; i++) {
        cout << res[i] << endl;
    }
    return 0;
} 

以上就是主要的代码和测试代码。原理其实也很简单。首先求出素数表，这边采用的是筛选法。有一个小技巧就是，数组的第一个元素用来记录该数组的有效位数，这样的一个好处就是可以重复的利用这个数组，从而避免反复开数组造成的浪费。

int prime[100000];
bool isPrime[1000005];
void getPrime(int x){
    for (int i = 1; i < x; i += 2) {
        isPrime[i] = 1;
        isPrime[i - 1] = 0;
    }
    prime[prime[0] = 1] = 2;
    for (int i = 3; ;i += 2) {
        if(isPrime[i]) {
            int j = i*i, k = i+i;
            if(j >= x) break;
            while(j < x) {
                isPrime[j] = 0;
                j += k;
            }
        }
    }
    for (int i = 3; i < x; i += 2) {
        if(isPrime[i]) {
            prime[++prime[0]] = i;
        }
    }
} 

以上就是求素数的代码, 通过不停地刷出含有约数的数，从而找到剩下的素数。

这里的时间复杂度为 O(N)。

然后，按照这个素数表，我们可以拿到小于这个数的所以素数。

int p[34380], cnt[34380];
void getPrimeDivisor( int x ) {
    p[0] = cnt[0] = 0; int t;
    for (int i = 1; prime[i]*prime[i] <= x  && i <= prime[0]; ++i) {
        t = 0;
        while (x%prime[i] == 0) {
            ++t; x /= prime[i];
        }
        if (t) {
            p[++p[0]] = prime[i];
            cnt[++cnt[0]] = t;
        }
    }
    if (x > 1) {
        p[++p[0]] = x;
        cnt[++cnt[0]] = 1;
    }
}; 

cnt 数组记录的是该数可以被这个素数约数除几次，p 表示的就是素约数。

从而我们获得了这样的一个对应关系，以 80 为例：

P:      2 5
CNT:    4 1 

这就表示，80 可以组成这样的一个等式 80 = 2^4 * 5。知道这个等式之后，我们就可以进行排列组合，将这两个素数排列出来。

vector<int> getDivisor(int x) {
    getPrimeDivisor(x);
    vector<int> divisor(1500);
    divisor[0] = 1;
    divisor[1] = 1;
    for (int i = 1; i <= p[0]; ++i) {
        int nowNum = divisor[0];
        int base = 1;
        for (int j = 1; j <= cnt[i]; ++j) {
            base *= p[i];
            for (int k = 1; k <= divisor[0]; ++k)
                divisor[++nowNum] = divisor[k]*base;
        }
        divisor[0] = nowNum;
    }
    return divisor;
} 

这个函数的意思就是，不停的组合数字。以 80 为例，我们可以依次获得， 1， 2， 4， 8， 16， 5， 10， 20， 40， 80，从而达到获得所有约数的目的。

这个方法获得某数的所有约数，他的时间复杂度远低于传统的 O(N)，虽然求素数表的操作是 O(N)，但是在多次求素数的时候，这个步骤可以共用。所以他的复杂度远低于传统的挨个判断。

所以，该方法还是不错的。