求质数的几种方法

暴力法

也称定义法

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

对于给定数字n，直接枚举j从1到n-1 ，如果j能够整除n，说明n不是质数

bool prime_simple(int num){
    if(num == 1)return false;
    for(int i = 2;i <= num - 1;i++)
        if(num % i == 0)return false;
    return true;
}

对于只是判断一个数字的时候，时间复杂度是O(n)，但是当我们需要判断某个区间的质数的时候，时间复杂度就上升到了O(n^2)。

简单优化

实际上枚举j到根号n就可以了，因为对于非质数num，存在a*b==num，若a和b均不为1，则a和b中必有且仅有一个大于等于根号num

bool prime_advanced(int num){
    if(num == 1)return false;
    for(int i = 2;i * i <= num;i++)
        if(num % i == 0)return false;
    return true;
}

对于只是判断一个数字的时候，时间复杂度是√n，但是当我们需要判断某个区间的质数的时候，时间复杂度就上升到了O(n√n)。

埃拉托斯特尼筛法

对于频繁求区间质数个数、区间跨度较大的情况，上面的方法效率很低，因为每次计算一个数字，都要从2进行枚举；我们换个思路想想，能够被质数整除的数字一定是合数（非质数），那我们直接将求得的质数，然后乘以相应的数字，得到的就一定是合数，将这些合数删去，不就只剩下了质数了吗？

筛选法的总体思路就是：首先假设序列num=2、3、4、5、……、n都是质数

• 2作为num的第一个质数，将2的倍数4,6,8,……,标记为合数
• 3作为num的第二个质数，将3的倍数6,9,12,……标记为合数
• 5作为num的第三个质数，将5的倍数10,15,20,……标记为合数

每次取序列中的一个数字a作为筛选的依据，在这里的a同样枚举到不超过√n即可。

#define MAXN 1000
bool isPrime[MAXN];
bool prime_super() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false, isPrime[0] = false;
    for (int i = 2; i * i <= MAXN; i++) {
        if (!isPrime[i]) continue;
        for (int j = i * i; j < MAXN; j += i) {
            isPrime[j] = false;
        }
    }
}

这里的时间复杂度我不太懂计算，但是至少比简单优化方法高效。

线性筛法--欧拉筛法

但是我们也会发现，有些数字被删除了好几次，比如说12，第一次被2删除，第二次被3删除；120分别被2、3、5删除，……，这样子我们的程序还是不够快，有没有办法能够确定每一个合数都只被删除一次呢？答案是有的，可以证明一个合数num的最小非1的因子一定是一个不大于√n的质数，利用这个性质，利用质数进行筛选的时候可以提前进行结束删除：

// 存放质数，可以不需要该数组，通过 isDeleted[] 也可以判断是否为质数，只不过使用
// prime[] 的速度可以更加快
#define MAXN 1000
int prime[MAXN];
bool isDeleted[MAXN];
int lastPrimeIndex = 0;
bool prime_extreme() {
    memset(isDeleted, false, sizeof(isDeleted));
    for (int i = 2; i < MAXN; i++) {
        if (!isDeleted[i]) prime[lastPrimeIndex++] = i;
        for (int j = 0; j < lastPrimeIndex && i * prime[j] < MAXN; j++) {
            isDeleted[i * prime[j]] = true;
            // 提前结束删除过程
            if (i % prime[j] == 0) break;
        }
    }
}