质数判断与质数筛

Posted on Waline:

什么是质数?

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

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。

可见 整除 对于质数的判断有很重要的作用

进而我们有质数判断的最基本的写法如下↓

质数判断 1.0

1
2
3
4
5
6
7
8
9
bool Isprime(int n)
{
    if (n == 1) return false;
    for(int i = 2; i < n; i++)
    {
        if(n % i == 0)  return false;
    }
    return true;
}

即对于 ， 不是 的因数

但是我们还能继续优化这个算法

质数判断 2.0

1
2
3
4
5
6
7
8
9
10
bool Isprime(int n)
{
    if (n == 1) return false;
    double sqrtn = sqrt(n);
    for(int i = 2; i < sqrtn + 1; i++)
    {
        if(n % i == 0)  return false;
    }
    return true;
}

即对于 ， 不是 的因数

注意其中的 double sqrtn = sqrt(n)语句的位置，这保证了 不会每次都被计算

质数判断 final 3.0（朴素筛）

朴素筛的时间复杂度是 

1
2
3
4
5
6
7
8
9
10
11
12
bool Isprime(int n)
{
    if (n == 1)  return false;
    if (n == 2)  return true;
    else if (n % 2 == 0) return false;
    double sqrtn = sqrt(n);
    for(int i = 3; i < sqrtn + 1; i+=2)
    {
        if(n % i == 0)  return false;
    }
    return true;
}

即对于 ，奇数 不是奇数 的因数

其实这里已经能看出来质数筛的思想了，就是逐步利用 质因子 筛去合数

质数筛法之埃式筛（埃拉托斯特尼算法）

埃氏筛的时间复杂度是

要得到自然数 以内的全部素数，必须把不大于 的所有素数 的倍数剔除，剩下的就是素数

例如：使用埃氏筛输出 100 以内的质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int n = 100;
int main() 
{
    bool R[n + 1];
    for (int i = 0; i <= n; i++) 
        R[i] = true; // 初始化所有数为素数

    for (int i = 2; i * i <= n; i++)
        if (R[i]) 
            for (int j = i * i; j <= n; j += i) 
                R[j] = false; //核心：剔除素数的倍数

    for (int i = 2; i <= n; i++) 
        if (R[i]) 
            cout << i << " "; //输出
    return 0;
}

下面，我们审视一下代码

1
2
3
4
for (int i = 2; i * i <= n; i++)
        if (R[i]) 
            for (int j = i * i; j <= n; j += i) 
                R[j] = false;

这里值得注意的地方是 j = i * i的初始化

为什么不从 开始算起呢？答案是 会被更小的素数筛去，这样做减少了重复筛除

能不能进一步优化呢？当然是可以的！

大名鼎鼎的欧拉筛

欧拉筛的时间复杂度是

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isprime[MAXN]; 
int prime[MAXN]; 
int n;
int cnt; 

void euler()
{
    memset(isprime, true, sizeof(isprime)); 
    isprime[1] = false; 
    for(int i = 2; i <= n; ++i)
    {
        if(isprime[i]) prime[++cnt] = i; // 记录素数
        for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
        {
            isprime[i * prime[j]] = false;  // 筛去i的质数倍
            if(i % prime[j] == 0) break; //直到遇到i的最小质因子
        }
    }
}

下面，我们审视一下这个代码的关键之处

1
2
3
4
5
for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
{
    isprime[i * prime[j]] = false;  //筛去i的质数倍
    if(i % prime[j] == 0) break; //直到遇到最小质因子
}

对于任意合数 (其中 为 的最小质因子)
那么，由于 , 会先进入筛子

关键： 的最小质因子不会小于 ，所以 会被它的最小质因子 筛去