质数筛
本文最后更新于298 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com

#include<iostream>
using namespace std;
bool isvis[20000];
int p[20000];
int c;
void get_prime(int n)		//O(nlog(logn)) 
{
	for(int i =2;i<=n;i++)
	{
		if(isvis[i] == false)
		{
			p[c++] = i;
			for(int j = i*2;j<=n;j+=i)
				isvis[j] = true;
		}
	}
}
void GetPrime(int n){	//O(n)
	for(int i =2;i<=n;i++)
	{
		if(isvis[i] == false)	p[c++] = i;
		for(int j = 0; p[j]*i <= n && j<=c;j++)
		{
			isvis[p[j]*i] = true;
			if(i%p[j]==0)	break;
		}
	 } 
}
int main(){
	int n;
	cin>>n;
	//get_prime(n);
	GetPrime(n);
	for(int i =0 ;i<c;i++)
		cout<<p[i]<<' ';
	return 0;
}
如果觉得本文对您有所帮助,那这将是对我最大的鼓励,期待您留下您宝贵的评论。
暂无评论

发送评论 编辑评论


				
上一篇
下一篇