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

1433 阅读 1 评论 0 点赞

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

9 人评分

本文分类：题解列表
浏览次数：1433 次浏览
发布日期：2019-06-13 20:24:01
本文链接：https://blog.dotcpp.com/a/60339

上一篇 > [编程入门]三个数字的排序-题解(C语言代码) 数组冒泡法排序
下一篇 > 字符串连接-题解(C++代码)

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

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

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

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

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

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

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

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

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

评论列表共有 1 条评论

发表评论取消回复

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

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

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复