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

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

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

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

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

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

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

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

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

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

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

评论列表共有 15 条评论

dotcpp0782798 5月前回复TA

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

dotcpp0782798 5月前回复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 7月前回复TA

好难理解埃筛啊

向志权 1年前回复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;
}

向志权 1年前回复TA

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

大帅哥 1年前回复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;
}

何豪 1年前回复TA

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

编程小顽石 1年前回复TA

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

Joker 2年前回复TA

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

dotcpp0610114 2年前回复TA

@dotcpp0610114 我搞错了

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

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

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 15 条评论

发表评论 取消回复

评论列表共有 15 条评论

发表评论取消回复