详解埃氏筛选法筛选素数（C++实现）_c++埃氏筛法

说明：篇中的n和N都是同一个意义，大小写不过是为了表现具体和一般形式而已，穿插着用可能让读者容易混淆，请多体谅。

一、质数定义

指在大于1的整数中，只能被1和它本身整除的数。

二、埃氏筛选法最重要的结论：

N有因数的话，那么至少有一半的因数不会超过$\sqrt{N}$。
举个例子，要判断100是不是质数，100 = 10 X 10，只要有1个因数 > $\sqrt{100}$，必然另1个因数 < $\sqrt{100}$，这样只要判断10以内有无100的因数即可，使用这种方法的时间复杂度为O(n*√n)。
可能这样你还不是很懂，继续往下看。

三、找到[0,n]范围内所有素数 的算法基本思路

1. 首先将0、1排除：

2. 创建从2到n的连续整数列表，[2,3,4,…,n]；

3. 初始化 p = 2，因为2是最小的质数；

4. 枚举所有p的倍数(2p,3p,4p,…)，标记为非质数（合数）；

5. 找到下一个 没有标记 且 大于p 的数。如果没有，结束运算；如果有，将该值赋予p，重复步骤4;

6. 运算结束后，剩下所有未标记的数都是找到的质数。

可以结合下面这张动图理解：

四、应用埃氏筛选法优化后的思路

我们发现 [0, N] 范围内很多 > $\sqrt{N}$的数其实是[0, $\sqrt{N}$]范围内数的倍数。而 > $\sqrt{N}$ 且 非[0, $\sqrt{N}$]范围内数字的倍数的，都是质数。
举个例子： [0, 100] 范围内很多 > $\sqrt{100}$的数其实是[0, $\sqrt{100}$]范围内数的倍数（12,14,16是2的倍数，12,15,18是3的倍数…）。而 > $\sqrt{100}$ 且 非[0, $\sqrt{100}$]范围内数字的倍数的（11,13,17…），都是质数。

所以对 标题三 的基本算法思路做出如下优化：
对于步骤4，可以不用从2p开始排除，而是直接从 $p^2$ 开始。理由已经在开始讲过，所有的小于 $p^2$ 的合数都有更小的因数而被排除。

对于步骤5，当 $p^2$ > n 的时候停止计算。

参考链接：
《使用埃拉托色尼筛选法在21亿内快速查找质数》
《埃拉托色尼筛选法巧解质数问题》

当范围在int范围内：

#include<iostream>
#include<cstdio>
using namespace std;
    
const int maxn=5000000;
long prime[maxn];    // 存储一个个确定为质数的数
bool is_prime[maxn+1];    // 标记范围内所有数
int p = 0;
int sieve(int n)
{
 	p = 0;
	for(int i=0;i<=n;i++)
		is_prime[i]=true;       // 所有数先标记为true
    is_prime[0] = is_prime[1] = false;   // 把数字0，1标记为质数
    for(int i=2;i<=n;i++)
    {
       	if(is_prime[i])         // 如果这个数没有被标记为false
    	{
             prime[p++]=i;       // 用prime数组存起来这个数，既存起了质数，又用p表示了质数个数
             for(int j=i*i;j<=n;j+=i)   // 这里没有优化时的写法是for(int j=2*i; j<=n; j++)。
	    	//因为小于j(即i^2)内的合数都因为(根号j)(即i)内有更小的j的的因数而被排除
    							// 比如3^2 = 9，为什么不算2*3 = 6呢， 因为6<9,所以6因为3以内有更小的因数而直接被排除
    				is_prime[j]=false;
        }
    }
    return p;          // 返回质数个数
}
int main()
{
	int n;
	while(~scanf("%d",&n))
    {
    	printf("质数个数是: %d\n",sieve(n));
    	printf("质数有:\n");
    	for (int i = 0; i<p; i++)
    	{
    		printf("%d ", prime[i]);
    		printf("\n\n");
        }
   	}
    system("pause");
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

当范围超过了int

static const int N = 1e7;
bool is_prime[N];   // 判断是否是素数
ll prime[N];       // 存储素数
ll sieve(ll num)
{
	int inx = 0;
	for (int i = 0; i<=N; i++)
		is_prime[i] = true;

	is_prime[0] = is_prime[1] = false;

	int MIN = (num > N) ? N : num;

	for (ll i = 2; i<=MIN; i++)
	{
		if (is_prime[i])
		{
			prime[inx++] = i;

			for (ll j = i*i; j<=num; j+=i)
				is_prime[j] = false;
		}
	}
	return inx;
}

int gcd(int inx)    // 此处由于传进来都是质数，所以直接相乘即为gcd
{
	int res = 1;
	for (int i = 0; i<inx-1; i++)
		res *= prime[i];
	return res;
}

void C3()
{
	ll num;     // 输入数
	int p;       // 最小公约数

	cin >> num;

	int inx = sieve(num);   // 筛选素数

	cout << gcd(inx) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45