筛选N以内的素数（常规筛+埃氏筛+欧拉筛）（C++代码）

4029 阅读 8 评论 7 点赞

[判断素数算法【推荐点击】](https://blog.csdn.net/huang_miao_xin/article/details/51331710 "判断素数算法【推荐】")

```
在讲埃拉托斯特尼筛法的思路前前，先讲一下大家一般能够想到的思路。其实求素数个数的方法有很多种，萌新现在不宜追求过多种解法，一般会一两种就足够解决大部分素数的题目了。大佬就最追求完美筛吧。
```

**常规筛**
```
1.输入一个n,求1-n之间的素数，那么肯定要有一个循环将1到n都过一遍。
2.判定素数，除了1和它本身外没有其它的因数，所以，这里也要有一层循环，将2-n-1之间的数都判断一遍。
3.根据题目要求输出。
```

```
#include<iostream>
using namespace std;
int main(){
	int n,flag;
		cin>>n;
		for(int j=2;j<=n;j++){
			flag=1;//
			for(int i=2;i*i<=j;i++)
				if(j%i==0){
					flag=0;
					break;
				}
				if(flag==1)
					cout<<j<<endl;
		}
	return 0;
}
```
**优化点：**
```
1.首先要有一个标志位flag，事先标记为1，说明这个j是素数，在第二层循环中，只要有j可以被整除，那么就将其标记为0，退出第一层循环，紧解输出。
```
```
2.通常萌新们在第二层循环的条件部分写i<n,这样时间复杂度为O(n^2),不太好。
```
```
3.再优化一下，i<=j/2;聪明一点的萌新会发现，我只要判断到j的一半就行了，因为小于j一半的因数的个数和大于j一半的因数的个数是相等，也就是以j的一半为界成对出现。 这样时间复杂度就为O（n^2/2），好像还行，但阶数没有降下来。数据规模很大的话1/2就没有意义了。
```
```
4.再优化一下，i*i<=j;或者i<=sqrt(j) 其实已经有数学给出了证明，j的因数是以j的方根对半分布的，也就是说，小于j的方根的因数的个数和大于j方根的因数的个数是相等。这样时间复杂度就为O(nsqrt(n)) ,这样的话已经不错了，足够解决大部分的相关问题了。
```

------------
```
	   
补充：(一，首先脑子要有一个基本的模型解法或者基本思路，学习的话就根据前辈的思路走，不要直接看代码，先实操；二，建议从网上多阅读一些有关时间复杂度的资料，这样可以逐步建立代码优化的方向，空间复杂度和代码复杂度就略过了，不太重要。三，其实还有其它的优化方法来提高运行速度，优化思路增加约束（去除很明显不必或重复计算的）)
```

------------

**埃氏筛**
```
基本思路：
首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数......

上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。

复杂度为O(nlogn)
```

```
#include<iostream>
using namespace std;
int main(){
    long long max=200000;
    long long  a[max],i,j;//可以计算到max
    long long n;
    cin>>n;
    a[0]=0;
    for(i=1;i<=n;i++)
        a[i]=i;//赋对应值 
        a[1]=0;
    for(i=2;i<=n;i++){
        if(a[i]==0)//被标记为零不是质数，
            continue;//跳过下面代码部分，直接进入下一次循环
        cout<<i<<endl;//筛出来的就是质数 输出
        for(j=i;i*j<=n&&j<n;++j)//就是上面写的基本思路
            a[i*j]=0;
    }
	return 0;
}
```

------------

**欧拉筛**
```
线性筛，复杂度为O(n)。与埃氏筛相比，不会对已经被标记过的合数再进行重复标记，故效率更高。欧拉筛将合数分解为 (最小质因数 * 一个合数) 的形式，通过最小质因数来判断当前合数是否已经被标记过。
```
```
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000;   // 表长
int prime[maxn], pNum = 0;    // prime记录素数，pNum记录素数个数
bool p[maxn] = {false};    // p记录当前数是否被筛去

void eulerSieve(int n) {// 查找记录2-n的素数{
    for (int i = 2; i <= n; i++){
        if (p[i] == false)  // 如果未被筛过，则为素数
            prime[pNum++] = i;

for (int j = 0; j < pNum; j++){

if (i * prime[j] > n) // 当要标记的合数超出范围时跳出
                break;

p[i * prime[j]] = true; // 将已经记录的素数的倍数进行标记
            if (i % prime[j] == 0)  //关键步骤
                break;
        }
    }
}
int main(){
    int n;
    int i;
    scanf("%d",&n);
    eulerSieve(n);
     for(i=0;i<pNum;i++)
        printf("%d\n",prime[i]);
    return 0;
}

```
```
欧拉筛的难点就在于对if (i % prime[j] == 0)这步的理解，当i是prime[j]的整数倍时，记 m = i / prime[j]，那么 i * prime[j+1] 就可以变为 (m * prime[j+1]) * prime[j]，这说明 i * prime[j+1] 是 prime[j] 的整数倍，不需要再进行标记(在之后会被 prime[j] * 某个数 标记)，对于 prime[j+2] 及之后的素数同理，直接跳出循环，这样就避免了重复标记。
```

赠人玫瑰，手有余香。点个赞吧。^-^

0.0分

39 人评分

本文分类：题解列表
浏览次数：4029 次浏览
发布日期：2019-06-12 04:48:57
本文链接：https://blog.dotcpp.com/a/60294

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

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

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

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

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

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

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

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

评论列表共有 8 条评论

aviyet 4年前回复TA

@aviyet @city 哦，谢谢

city 4年前回复TA

@aviyet printf("%d
"); 这一句没有参数哦

aviyet 4年前回复TA

@aviyet 运行了是对的啊

aviyet 4年前回复TA

萌新一枚，最简单的方法为啥不给过啊：
#include <stdio.h>
int func(int n) {
	for (int i=2; i<n; i++) {
		if (n%i == 0) {
			return 0;
		}
	}
	return 1;
}
int main(void) {
	int n;
	scanf("%d", &n);
	for (int i=2; i<=n; i++) {
		if (func(i)) {
			printf("%d\n");
		}
	}
	return 0;
}

卵不知道 5年前回复TA

欧拉筛没看懂。

灰太狼 5年前回复TA

很棒，谢谢

myaijarvis 5年前回复TA

没看懂，哈哈！

ppp 5年前回复TA

学习到了--

筛选N以内的素数（常规筛+埃氏筛+欧拉筛） （C++代码）

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

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 8 条评论

发表评论 取消回复

筛选N以内的素数（常规筛+埃氏筛+欧拉筛）（C++代码）

评论列表共有 8 条评论

发表评论取消回复