素数之筛法

本文主要介绍总结一下判定素数过程中使用的两种筛选方法——Eratosthenes筛法(Sieve of Eratosthenes)和Eular筛法(Sieve of Euler)。

Eratosthenes筛法

基本思想：

素数的倍数一定不是素数

实现方法

• 使用长度为N的数组保存数字素数信息（0表示是素数，1 表示非素数）
• 首先将数组初始化为0，即认为所有的数都是素数
• 从第一个素数2开始，把所有2的倍数都记为素数（即将数组对应值置为1），一直到超出N的范围；
• 然后进行3的遍历，执行相同的操作；
• 执行到4的时候，由于之前已经将其值置为1，即判定为非素数，则执行++对下一个素数5进行操作；
• 依次进行上述操作，直到最后可以获得所有的素数。

举例操作（N=20）

i	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2			1		1		1		1		1		1		1		1		1
3					1			1			1			1			1
5										1					1				1
7													1
ALL	0	0	1	0	1	0	1	1	1	0	1	0	1	1	1	0	1	0	1

0： 素数
1：非素数

代码实现

#include <iostream>
using namespace std;
int main()
{
    int num;
    cin >> num;
    int flag[1000] = {0};
    int prime[1000];
    int count = 0;
    for(int i = 2; i < num; ++i)
    {
        if(!flag[i])
            prime[count++] = i;
        for(int j = i + i; j <= num; j += i)
            flag[j] = 1;
    }
    cout << "The number is: " << count << endl;
}

此算法的时间复杂度是O(nloglogn)，空间复杂度是O(n)；
由上也可以看出，此算法有很多不足之处，比如6，在素数为2时处理过一次，在为3的时候也处理了一次，重复了相同的操作。下面我们将介绍一个改进算法，欧拉筛法。

Euler筛法

核心思路

规定每个合数只用最小的一个质因数去筛选，比如6有2和3两个因数，只用2进行筛选和置位操作，3的情况通过条件跳过。

举例操作（N=20）

i	j	p[j]	count	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	2	1			1
3	0	2	2					1
3	1	3	2								1
4	0	2	2							1
5	0	2	3									1
5	1	3	3														1
6	0	2	3											1
7	0	2	4													1
8	0	2	4															1
9	0	2	4																	1
10	0	2	4																			1
ALL				0	0	1	0	1	0	1	1	1	0	1	0	1	1	1	0	1	0	1

0： 素数
1：非素数

代码

下面直接上代码

#include <iostream>
using namespace std;
#define Length 1000000
int main()
{
    int num;
    cin >> num;
    int flag[Length] = {0};
    int prime[1000];
    int count = 0;
    for(int i = 2; i <= num; ++i)
    {
        if(!flag[i])
        {
            prime[++count] = i;
        }
        for(int j = 1; j <= count; ++j)
        {
            if(i * prime[j] > num)
                break;
            flag[i * prime[j]] = 1;
            if(i % prime[j] == 0)
                break;
        }
    }
    cout << count << endl;
}

代码分析

核心代码 if(i % prime[j] == 0) break；

• 保证了每个合数都被置位
• 每个合数只会筛选到一次，在取其最小质因子的情况下

Eular算法的时间复杂度为O(n)，相较之Eratosthenes算法有了很大的提升。