[编程入门||算法进阶]筛选N以内的素数（C++代码），真正の筛法求素数教学

2174 阅读 6 评论 3 点赞

首先，大家都了解素数的定义，所以根据定义，该题有了如下写法(大多数题解的写法)
```cpp
#include<bits/stdc++.h>
using namespace std;
int judge(int x)//判断是否为素数 
{
	
	if(x==2) return 1;
	//下面一行可以改为for(int i=2;i*i<=x;i++)原因见数学分析 
	for(int i=2;i<x;i++)
	{
		if(x%i==0) return 0;
	}
	return 1;
}
int main()
{
	int n;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		if(judge(i)) cout<<i<<endl;
	}
}
```
但是，这种写法效率特别低下，在数字大的时候，绝对会超时，这时候我们可以利用**真正の筛法****，于是有了如下代码
```cpp
#include<bits/stdc++.h> 
using namespace std;
bool f[1000005];//f[i]为0代表i不是素数，为1代表是素数 
int main()
{
  int n; 
  cin>>n;
  f[1]=0;
  for(int i=2;i<=n;i++)//先把全部初始化为素数，1为特例 
  f[i]=1;
  for(int i=2;i<=n;i++)
  {
    if(f[i]==1)
    {
      for(int j=2;j*i<=n;j++)//素数的倍数一定不是素数 
      f[i*j]=0;
    }
  }
  for(int i=2;i<=n;i++)
  if(f[i])
  cout<<i<<endl;
}

```
这是普通的筛法，效率比上面的代码来说高了很多，但仍然存在不足。
不足之处在于，***举个栗子*******，2的倍数是4,6,8,10.....，但4的倍数又是8,12.....就造成了多次重复的赋值，所以引申
# **欧拉函数的方法(欧拉筛法)**
```cpp
#include<bits/stdc++.h>
using namespace std;
int p[50000];
int ans[50000];
int t=0;
void getans(int n)
{
	memset(p,0,sizeof(p)); 
	for(int i=2;i<=n;i++)
	{
		if(!p[i]) ans[t++]=i;//将素数存入ans中 
		for(int j=0;j<t&&i*ans[j]<=n;j++)
		{
			p[i*ans[j]]=1;//关键循环，把所有素数的n倍都标记为非素数，这就是筛法 
			if(i%ans[j]==0) break;//欧拉筛法关键步骤，详情搜索欧拉函数 
		}
	}
}
int main()
{
    int n;
    cin>>n;
    getans(n);
    for(int i=0;i<t;i++) cout<<ans[i]<<endl;
}
```
便是非常效率的写法了，详细步骤已在代码的注释中标注。有一些难理解，但作为一个背板男问题不大。
## 这便是学习算法的一个关键步骤，不是ac了就好，而是追求完美
wawa,希望大家耐心的学习一下筛法，比赛的时候相当有用噢(min25筛天下第一！！！！)

0.0分

15 人评分

本文分类：题解列表
浏览次数：2174 次浏览
发布日期：2019-06-12 00:03:20
本文链接：https://blog.dotcpp.com/a/60292

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

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

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

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

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

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

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

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

评论列表共有 6 条评论

ajsdashjbd 5年前回复TA

@ajsdashjbd 你说的那个，是利用积性函数的性质来在O（n）时间内筛出该积性函数的值，希望弄懂再发题解，再反驳

ajsdashjbd 5年前回复TA

@ajsdashjbd 利用的是欧拉函数和它本身不同质因数的关系。。。。请问复制百度百科有意思?你好好看看那条百度百科，那讲的是利用欧拉晒筛欧拉函数，欧拉筛利用的叫做容斥原理，就是让每个数只被它最小的质因数所筛出来，因此避免了冗余才打到O（n）复杂度，求发题解最起码先弄明白，而不是似懂非懂，这样会误导很多人

Reskyd 5年前回复TA

@ajsdashjbd 利用的是欧拉函数和它本身不同质因数的关系鸭

ajsdashjbd 5年前回复TA

欧拉筛跟欧拉函数除了都带个欧拉还有啥关系呢

ajsdashjbd 5年前回复TA

欧拉筛跟欧拉函数除了都带个欧拉还有啥关系呢

ajsdashjbd 5年前回复TA

欧拉筛跟欧拉函数除了都带个欧拉还有啥关系呢

[编程入门||算法进阶]筛选N以内的素数 （C++代码），真正の筛法求素数教学

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

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 6 条评论

发表评论 取消回复

[编程入门||算法进阶]筛选N以内的素数（C++代码），真正の筛法求素数教学

评论列表共有 6 条评论

发表评论取消回复