01 质数筛

发布时间:2024年01月24日

一、根据概念进行枚举

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的约数是成对存在的,一个小于\sqrt{n},另外一个则大于\sqrt{n},可以举例理解,对于一个1~\sqrt{n}的约数,则有一个\sqrt{n}~n的约数与之对应,所以判断n有没有约数只要判断前面1~\sqrt{n}的范围的即可,时间复杂度为O(\sqrt{n})

//输入一个数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个数

循环次数为:

\frac{n}{2}-1+\frac{n}{3}-1+....\frac{n}{n}-1=n*(\frac{1}{2}+\frac{1}{3}+....\frac{1}{n})-(n-1)

对于\frac{1}{2}+\frac{1}{3}+....\frac{1}{n}是一个调和级数,其值等于\ln n+C,带入上述公式结果为:

n*(\ln n+C)-n+1=n*(\ln n+C-1)+1

去掉常数项,总的时间复杂度为O(n\ln 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)

文章来源:https://blog.csdn.net/xuqw11111/article/details/135814066
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。