要么改变世界,要么适应世界

求质数的几种方法

2020-10-03 22:32:47
118
目录

暴力法

也称定义法

质数是指在大于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,若ab均不为1,则ab中必有且仅有一个大于等于根号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;
        }
    }
}
历史评论
开始评论