筛选N以内的素数详解（C++代码）（小白向）

10323 阅读 15 评论 0 点赞

原题链接：[编程入门]筛选N以内的素数

前排观影提示：```素数 == 质数```

# Part 1 暴力？

~~暴力部分在2019年的时候已经写过了，这里整理下。（啥我19年就入坑了？）[链接](https://www.luogu.com.cn/blog/pang223/prime-array)~~

本题要求我们求n以内的素数，首先我们回到素数的定义上去。

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

翻译一下，就是出了1和自己可以整除外，其他数都不能被素数整除。

这就非常amazing了啊，我们只需要枚举每一个大于二的自然数，然后让它一个一个整除比它小的数。

```cpp
// 纯暴力无优化代码
#include <cstdio>
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i) {
        bool isPrime = true;
        for (int j = 2; j < i; ++j) {
            if (i % j == 0) {
                isPrime = false;
            }
        }
        if (isPrime) {
            printf("%d\n", i);
        }
    }
    return 0;
}
```

#### 优化: j * j <= i

每一次我们判定是否为素数时都需要枚举到```j < i```，是否能将范围缩小呢？

所有合数都可以写成```j * k```，其中，**j、k是可以互换位置的**。
由于可互换，所以当```j * j <= i``` 的时候，将j、k位置互换，整个过程就可以转化为j从2开始增大，然后到```j * j <= i```时又开始缩小，相当于是**算了两遍**。

```cpp
// 优化1
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i) {
        bool isPrime = true;
        for (int j = 2; j * j <= i; ++j) {
            if (i % j == 0) {
                isPrime = false;
            }
        }
        if (isPrime) {
            printf("%d\n", i);
        }
    }
    return 0;
}
```

#### 优化：跳过合数

**因为合数可以分解成很多个质数**，所以在除合数的时候，相当于除了很多个质数，这时候我们就需要一个**质数表**，来存储比当前i小的质数，每一次除质数就可以了。

代码就暂时不放了。

### 总结

时间复杂度：
- 不优化：```n ^ 2```
- sqrt优化：```sqrt(n)*n```
- 跳过合数：```未知，但是随着n的变大，质数越来越稀疏，接近nlogn？```

但是，这三种中都使用了取模操作，这个操作的常数非常大，所以速度**比较慢**

那么有什么方法能不用取模呢？

# Part 2 埃筛

我们看一下题目：**筛选**N以内的素数。
所以正解肯定是筛选法啊。

整个算法的过程如下：
1. 创建一个bool的数组a，用于记录a[i]是否为质数，默认为false，false即为质数，true为合数。
2. i从2开始遍历，直到n，如果```!a[i]```（i为质数），将每一个i的倍数（不包括自己）标志成合数。

细想想，只有i不是质数才能开始标记，不就是**part1的跳过合数优化**吗？
而且，整个算法没有用到取模，**常数大大降低**，但是**合数会被不同的质因子反复标记**，所以时间复杂度大概在```nlognlogn```左右。

```cpp
// 埃筛
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N = 10000;

bool a[MAX_N];

int main()
{
    int n;
    scanf("%d", &n);
    memset(a, 0, sizeof(a));
    a[0] = true;
    a[1] = true;
    for (int i = 2; i <= n; ++i) {
        if (!a[i]) {
            for (int j = 2; i * j <= n; ++j) {
                a[i * j] = true;
            }
            printf("%d\n", i);
        }
    }
    return 0;
}
```

#### 优化：sqrt()

没错，我经过百度了一下发现，埃筛也可以做到part1的这个优化。

让```j```从```i```开始，而不是从```2```开始，是因为前面的都被其他质数筛过一遍了。

```cpp
// 优化的埃筛
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N = 10000;

bool a[MAX_N];

int main()
{
    int n;
    scanf("%d", &n);
    memset(a, 0, sizeof(a));
    a[0] = true;
    a[1] = true;
    for (int i = 2; i <= n; ++i) {
        if (!a[i]) {
            for (int j = i; i * j <= n; ++j) {
                a[i * j] = true;
            }
            printf("%d\n", i);
        }
    }
    return 0;
}
```

复杂度疑似在```sqrt(n)log(n)```左右，可以归为```nlogn```一类。

-----------------
#### 写在最后
1. 除了埃筛，还有一种**欧拉筛**，做到了```O(n)```的时间复杂度，比```nlogn```要快很多，想了解的同学可以参考[**这篇文章**](https://www.cnblogs.com/cicos/p/10258703.html)，里面有线性复杂度证明。
2. 跳过合数的这个词切勿用在与dalao交流的过程中，因为这个词是我自己创的（？）
3. 如果我的代码被你hack了请及时告知我，并给出hack样例，谢谢。

参考：

1. [欧拉筛法（线性筛）的学习理解](https://blog.csdn.net/qq_39763472/article/details/82428602)
2. [线性筛素数 - 欧拉筛 （包含正确性和复杂度的证明）](https://www.cnblogs.com/cicos/p/10258703.html)

0.0分

36 人评分

本文分类：题解列表
浏览次数：10323 次浏览
发布日期：2021-02-05 13:32:53
本文链接：https://blog.dotcpp.com/a/76390

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 15 条评论

dotcpp0610114 2年前回复TA

define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

int main(){
	int a, i=3;
	scanf("%d", &a);
	printf("2\n");
	for (;i <= a;i++) {
		if (i%2!=0&&i%3!=0&&i%5!=0&&i%7!=0) { printf("%d\n", i); }
		}
	return 0;
}这个才好懂

lin233 2年前回复TA

循环可以每次+2，还能节省不少时间

wrinkle 2年前回复TA

#include<stdio.h>
int main()
{
    int n;
	scanf("%d",&n);
    if(n>=2)
    {
    	printf("2\n");
	}
    for(int i=2;i<=n;i++)
    {
    	for(int k=2;k<=i-1;k++)
    	{
    		if(i%k==0)
    		{
    			break;
			}
			else
			{
				printf("%d\n",i);
				break;
			}
		}
	}
	return 0;
}

末日流光 3年前回复TA

欧拉筛
#include <iostream>
#include <string.h>
using namespace std;
typedef  long long LL;
LL prime[100001];
bool vir[100000001];
int main()
{
	memset(prime,0,sizeof(prime));
	memset(vir,0,sizeof(vir));
	LL n;
	cin>>n; 
	vir[1]=true;
	for(LL i=2;i<=n;i++){
		if(!vir[i]){
			vir[i]=1;
			prime[++prime[0]]=i;
		}
		for(LL j=1;j<=prime[0]&&i*prime[j]<=n;j++){
			vir[prime[j]*i]=true;
			if(i%prime[j]==0) break;
		}
	}
	//cout<<prime[0];
	for(int i=1;i<=prime[0];i++)
	cout<<prime[i]<<endl;
	return 0;
}

学子 3年前回复TA

学到了

筛选N以内的素数详解（C++代码）（小白向）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 15 条评论

发表评论 取消回复

评论列表共有 15 条评论

发表评论取消回复