Reskyd

用户名：a756256994

访问量：15502

签　名：

无事勿扰

等　　级
排　　名	922
经　　验	3476
参赛次数	7
文章发表	5
年　　龄	18
在职情况	学生
学　　校
专　　业	计科

　　自我简介：

铁牌选手/数论只会骗子/数据结构只会暴力

TA的其他文章

用筛法求之N内的素数。 -题解(C++代码)，普通写法，筛法，欧拉筛法全讲解
浏览：1289

你可能喜欢

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

　　作者: Reskyd　　　　发表时间：2019-06-12 00:03:20 浏览：2115　|　评论：3　

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

首先，大家都了解素数的定义，所以根据定义，该题有了如下写法(大多数题解的写法)
```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分

16 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

ajsdashjbd

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

2019-06-12 10:02:12

Reskyd 2019-06-12 10:55:55 |

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

ajsdashjbd 2019-06-12 17:06:41 |

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

ajsdashjbd 2019-06-12 17:09:38 |

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

ajsdashjbd

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

2019-06-12 10:01:56

ajsdashjbd

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

2019-06-12 10:01:38

Reskyd

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-字符串正反连接（C语言代码）

打水问题（C语言代码）

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

评论区

精彩推荐

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-阶乘数列（C语言代码）

WU-输入输出格式练习（C++代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

1017题解

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

Reskyd

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

打水问题 （C语言代码）

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

评论区

精彩推荐

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

WU-输入输出格式练习 （C++代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

1017题解

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言训练-字符串正反连接（C语言代码）

打水问题（C语言代码）

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

　　评论区

母牛的故事（C语言代码）

C二级辅导-阶乘数列（C语言代码）

WU-输入输出格式练习（C++代码）

用筛法求之N内的素数。（C语言代码）