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

11634 阅读 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 人评分

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

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

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

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

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

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

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

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

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

评论列表共有 15 条评论

dotcpp0782798 2年前回复TA

@李在fitting 不好意思兄弟，等级不够不能直接评论，格式整理不好

dotcpp0782798 2年前回复TA

@李在fitting 我只能说，每次代码都没毛病，它硬打给我0分                                                                                         #include<stdio.h> int main() {     int n;     printf("请输入一个正整数\n");     scanf("%d", &n);     printf("\n2\n");     for (int i = 2; i < n + 1; i++)     {         for (int u = 2; u < i; u++)         {             if (i % u == 0)             {                 break;             }                         else if(u ==i - 1 && i % u !=0)             {                                                       printf("%d\n", i);                                               }                           }          }     return 0;   }

李在fitting 2年前回复TA

好难理解埃筛啊

向志权 2年前回复TA

#include<stdio.h>
int main()
{
	int i,j,N;
	int x;
	printf("请输入N，用简单素数筛选法求N以内的素数。\n");
	scanf("%d",&N);
	printf("这其中有\n");
	if(N<=1)
		printf("无\n");
	else
	{
		printf("2\n");
	for(i=3;i<=N;i++)
	{
		x=0;
		for(j=2;j<i;j++)
		{
			if(i%j==0)
				x++;
		}
		if(x==0)
		printf("%d\n",i);
	}
	}
	return 0;
}

向志权 2年前回复TA

@wrinkle 你这个输出只是奇数，不是质数

大帅哥 2年前回复TA

帮我看看这个怎么错了
#include<math.h>
#include<stdio.h>
int main()
{
    int i,n,N,k;
scanf("%d",&N);
for(n=2;n<=N;n++)
{

k=sqrt(n);
for(i=2;i<=k;i=i++)
   {
       if(n%i==0) break;
   }
if(i>k)
    printf("%d",n);
}
	return 0;
}

何豪 2年前回复TA

@dotcpp0610114 不对啊，我思路跟你一样，但是数越大之后，筛选能力会变小很大

编程小顽石 3年前回复TA

@Joker 是有优化的遍历数量少了一半

Joker 3年前回复TA

除了2，好像素数都是奇数吧，我能只遍历奇数，然后从中去筛选出素数，会有一定优化么？

dotcpp0610114 3年前回复TA

@dotcpp0610114 我搞错了

编程教程

视频网课

题解博客

编程教辅指南

编程问答

MySQL教程

JavaScript教程

Web网站搭建与管理

MCI多媒体编程

C语言图形编程

CSS教程

HTML教程

算法竞赛教程

趣味项目教程

ACM与蓝桥杯竞赛指南

Socket套接字编程

Linux命令

Java教程

C语言函数库

编译器教程

Python教程

单片机教程

数据结构教程

C++教程

C语言教程

计算机二级C语言

QT开发

代码模板

STL库教程

MySQL函数库（超级全面）

PHP教程

Docker教程

全部教程

编程训练

蓝桥杯真题

编程零基础习题

数据结构配套题

信息学一本通 C/C++ 基础

信息学一本通 基础算法

ACM 蓝桥杯竞赛入门

OpenJudge 题库

Java 程序设计配套习题

信息学一本通 数据结构

Python 入门编程题库

谭浩强 C 语言课后习题

Python程序设计配套习题

信息学一本通提高篇

凌云训练

全部编程训练

全部题目

编程考试

C语言试卷

C++试卷

CSP考试

数据结构与算法

计算机二级

Java试卷

考研真题

Linux

Mysql数据库

计算机网络

NOIP真题

Python试卷

高校题库

人工智能

软件工程

全部试卷

团队教学

全部团队

比赛列表

创建比赛

创建团队

AI 编程

码曰编程

代码解释

代码转换

代码纠错

代码生成

Mysql 转换

编程助手

信息学一本通基础算法

信息学一本通数据结构

评论列表共有 15 条评论

发表评论取消回复