C++质数判断算法的时间测试

C++质数判断算法的时间测试

测试标准

这里使用两类、五种常用质数判断算法进行测试:枚举因子法(暴力、开方优化、6n再优化)、质数筛(埃氏筛法、欧拉筛法)。(Miller-Rabin呢?不会,没搞懂)

同时,使用两类情况进行测试:

  1. 寻找 2-100,000 内的质数个数
  2. 寻找 10,000,001-10,009,999 内的质数个数

质数判断算法

枚举因子法

1. 暴力遍历

很显然,判断n是不是质数,最简单的只要暴力从2到n过一遍就可以了

template <class IntT> bool isPrime(IntT n) {
    if (n <= 1)
        return false;
    for (IntT i=2; i<n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

分析:最坏情况(是质数)每个都遍历一遍,时间复杂度(O(n)),平均情况由于质数分布也是(O(n))

2. 开方优化

容易推出,若一个数n不是质数,则它必然有一个因数(Flesqrt{n})。因此,只需要判断 [2-(sqrt n)]之间的数即可。

template <class IntT> bool isPrime(IntT n) {
    if (n <= 1)
        return false;
    for (IntT i=2; i*i<=n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

分析:时间复杂度降为(O(sqrt n))

3. 6n优化

再想一想就会发现,我们对于2、3的倍数做了太多次重复运算:一个数模2不等于0,那么它模4、6、8也都不会等于0;3也一样。这些重复在6次的周期内会重复4次。因此,我们可以考虑优化它们,即:
除特殊情况外,只需考虑因数为(6n-1)和(6n+1)的情况(n为正整数)

template<class IntT> bool isPrime(IntT n) {
    if (n <= 1)
        return false;
    if (n <= 5 && n != 4)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (IntT i=5; i*i<=n; i+=6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

分析:虽然时间复杂度没降,但速度显著提升了

筛法

这里就不详细讲解了,主要是运用已知的质数遍历,减少求范围内质数时重复的遍历次数(筛法都会更耗空间)。

1. 埃氏筛法

(注:这里加了个小小的优化,在第二层循环里,j初始化为i*i

template<class IntT> IntT get_primes_num(IntT n) {
    if (n <= 1)
        return 0;
    bool *isPrimes = new bool[n + 1];
    IntT *primes = new IntT[n - 1],
         pn = 0;
    memset(isPrimes, 1, n - 1);
    for (IntT i=2; i<=n; i++) {
        if (isPrimes[i]) {
            primes[pn++] = i;
            for (IntT j=i*i; j<=n; j+=i)
                isPrimes[j] = false;
        }
    }
    delete isPrimes;
    delete primes;
    return pn;
}

时间复杂度为(O(nlnln n))(这一堆原理自己搜去,我自己也讲不清楚)

2. 欧拉筛法

对于埃氏筛法的进一步优化

template<class IntT> IntT get_primes_num(IntT n) {
    if (n <= 1)
        return 0;
    bool *isPrimes = new bool[n + 1];
    IntT *primes = new IntT[n - 1],
        pn = 0;
    memset(isPrimes, 1, n - 1);
    for (IntT i=2; i<=n; i++) {
        if (isPrimes[i])
            primes[pn++] = i;
        for (IntT j=0; i*primes[j]<=n; j++) {
            isPrimes[i * primes[j]] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
    delete isPrimes;
    delete primes;
    return pn;
}

时间复杂度为(O(n))。注意:在n不大的时候,欧拉筛法与埃氏筛法比并不具有绝对优势,还有可能被反超(毕竟只是优化了个(lnln n)),几乎相当于拼常数

测试

好了,接下来就是我们的核心——测试环节了。我这里在本机使用了一个基于std::chrono的封装计时库(程序主体部分运行至少6s)。记录以微秒(μs,百万分之一秒)为单位。
(windows x64 AMDRyzen5-5600H)

回顾一下两种情况:

  1. 寻找 2-100,000 内的质数个数
  2. 寻找 10,000,001-10,009,999 内的质数个数(筛法:你故意找茬是吧)
平均用时(μs) 情况1 情况2
暴力遍历 647,400 8,800,000
平方优化 3,985 3,496
6n优化 1,363 1,163
埃氏筛 154.5 35,000
欧拉筛 265.5 50,000

总结

平时做算法题的时候,如果说是从1或者一个较小的数开始计数的,那么建议使用埃氏筛(欧拉筛实现起来更烦,还不一定拼得过加了优化的埃式筛法(ps:优化加了容易数据容易溢出,建议用unsigned long long),要么去掉优化老老实实用j=2i);
反之,如果是都在一个较高位的,那么建议使用6n优化,容易写,比平方优化效率也高很多。这时候再使用两次筛法的差值,时间就容易爆掉(就算一次也容易爆时间)。

好了,以上就是本人对C++质数判断算法的时间测试的所有内容了,初次创作,如有错误欢迎指出ヾ(^▽^*)))

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » C++质数判断算法的时间测试