01 质数筛

一、根据概念进行枚举

1、判断质数的枚举算法

根据概念:除了1和它本身以外没有其他约数的数为质数

//输入一个数n，判断n是不是质数
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	//根据概念:除了1和它本身以外没有其他约数的数为质数
	bool flag=1;
	for(int i=2;i<n;i++)  
		if(n%i==0){
			flag=0;
			break;	
		} 
	if(flag) cout<<"YES";
	else cout<<"NO";
	return 0;
}

2、枚举的范围进行优化

如果n有约数，则n的约数是成对存在的，一个小于,另外一个则大于，可以举例理解，对于一个1~的约数，则有一个~n的约数与之对应，所以判断n有没有约数只要判断前面1~的范围的即可，时间复杂度为O()

//输入一个数n，判断n是不是质数
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	bool flag=1;
	for(int i=2;i*i<n;i++) //枚举方式进行优化 
		if(n%i==0){
			flag=0;
			break;	
		} 
	if(flag) cout<<"YES";
	else cout<<"NO";
	return 0;
}

二、朴素筛法

思路分析：

从2到n进行遍历，对于遍历到的数如果没有被筛掉，就说明该数是素数。然后每次把遍历到的数i的倍数都筛去。为什么说这个方案可以筛出质数可行呢？因为对于一个数p，它如果没有被筛掉，就说明其不是前面2~p-1的倍数，也就是说2~p-1不存在p的约数，这不就是素数的定义！

代码实现：

//输入一个数n，输出1-n中质数的个数
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

bool st[N];
int prime[N],idx;
int main(){
	int n;
	cin>>n;
	for(int i=2;i<=n;i++){
		if(!st[i]) prime[++idx]=i;
		//用i筛掉后面i的倍数
		for(int j=i*2;j<=n;j+=i) st[j]=true;
	}
	cout<<idx<<endl;
	return 0;
}

时间复杂度分析?

对于数i来说：

i=2,筛掉n/2-1个数 (因为i是从2*i个数开始的，i不会被不能重复筛掉，所有要减一)

i=3,筛掉n/3-1个数

i=4,筛掉n/4-1个数

.......

i=n,筛掉n/n-1个数

循环次数为：

对于是一个调和级数，其值等于，带入上述公式结果为：

n*()-n+1=n*(-1)+1

去掉常数项，总的时间复杂度为O(n),等价于O(nlogn)

三、埃氏筛法

思路分析：

? 根据通过质数去把所有合数都删掉的思路，可以优化方一的普通筛法。（因为合数都可以以质数的乘积形式获得）

代码实现：

//输入n，输出1~n中质数的个数
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

bool st[N];
int prime[N],idx;
int main(){
	int n;
	cin>>n;
	for(int i=2;i<n;i++){
		if(!st[i]) prime[++idx]=i;
		else continue;
		//用i筛掉后面i的倍数
		for(int j=i*2;j<=n;j+=i) st[j]=true;
	}
	cout<<idx<<endl;
	return 0;
}

时间复杂度分析：O(nloglogn)

四、线性筛法

思路分析：

线性筛法的核心思路就是每个数只会被其最小质因子筛掉，因为每个数只有一个最小质因子，所以每个数都只会被删一次，所以是线性的。

代码实现：

//输入n，输出1~n中质数的个数
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

bool st[N];
int prime[N],idx;
int main(){
	int n;
	cin>>n;
	for(int i=2;i<=n;i++){
		if(!st[i]) prime[++idx]=i;
		
		for(int j=1;prime[j]*i<=n;j++){
			st[i*prime[j]]=true;
			//如果prime[j]是i的一个质因子,那么i乘以任何一个数的乘积都包含质因子prime[j]
			//如果继续筛下去对于k=i*prime[j+1],prime[j+1]肯定大于prime[j],使用prime[j+1]筛选k
			//而不是使用prime[j]筛选k，与线性筛的要求不符
			if(i%prime[j]==0) break;
		}
	}
	cout<<idx<<endl;
	return 0;
}

时间复杂度分析：O(n)

因为每个合数的最小质因子只有一个，所以每个数只会被筛掉一次，所以时间复杂度为O(n)