Reskyd

用户名：a756256994

访问量：15501

签　名：

无事勿扰

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

　　自我简介：

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

TA的其他文章

[编程入门]自定义函数之字符串拷贝-题解(C++代码)，STL大法好，string一键剪接函数substr讲解
浏览：1290

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

你可能喜欢

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

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

　　作者: Reskyd　　　　发表时间：2019-06-13 20:24:01 浏览：1289　|　评论：1　

原题链接：用筛法求之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分

11 人评分

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

　　评论区

jsq

头文件虽然那样写会很方便，但是会导致程序运行的时间变长，最好还是只把用的写出来，嘿嘿嘿~

2020-02-28 17:51:56

Reskyd

TA的其他文章

你可能喜欢

字符统计（C语言代码）

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

C语言训练-角谷猜想（C语言代码）

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

C二级辅导-等差数列（C语言代码）

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

评论区

精彩推荐

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

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

点我有惊喜！你懂得！

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

C语言训练-排序问题<2> （C++代码）（sort函数）

点我有惊喜！你懂得！

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

妹子杀手的故事（C语言代码）

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

最小公倍数（C语言代码）

Reskyd

TA的其他文章

你可能喜欢

字符统计 （C语言代码）

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

C语言训练-角谷猜想 （C语言代码）

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

C二级辅导-等差数列 （C语言代码）

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

评论区

精彩推荐

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

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

点我有惊喜！你懂得！

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

C语言训练-排序问题<2> （C++代码）（sort函数）

点我有惊喜！你懂得！

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

妹子杀手的故事 （C语言代码）

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

最小公倍数 （C语言代码）

字符统计（C语言代码）

C语言训练-角谷猜想（C语言代码）

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

C二级辅导-等差数列（C语言代码）

　　评论区

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

妹子杀手的故事（C语言代码）

最小公倍数（C语言代码）