快速求出某数的所有约数

故事是这样的,有一场比赛题,本来应该是考察 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),但是在多次求素数的时候,这个步骤可以共用。所以他的复杂度远低于传统的挨个判断。

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

版权所有:《Mike's Blog》 => 《快速求出某数的所有约数
本文地址:https://mikecoder.cn/post/183
除非注明,文章均为 《Mike's Blog》 原创,欢迎转载!转载请注明本文地址,谢谢。

发表评论

*