首页 > 代码库 > 素数筛选法
素数筛选法
今天发现了一个更快的素筛，比以前会的素筛速度快了整整一倍，虽然大部分题目不会对时间要求那么严格，但是会一个更快的算法还是很棒的。
以前用的素筛：
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int maxn=(1<<24)+1;bool isprime[maxn+5];int prime[maxn+5],cnt=0;void get(){ for(int i=2;i<=maxn;i++) { if(!isprime[i]) { prime[cnt++]=i; for(int j=i+i;j<=maxn;j+=i) isprime[j]=1; } }}int main(){ get(); cout<<cnt<<endl; printf("%d %d %d\n",prime[0],prime[1],prime[2]); return 0;}
更快的素筛：
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int maxn=(1<<24)+1;bool isprime[maxn+5];int prime[maxn+5],cnt=0;void get(){ for(int i=2;i<=maxn;i++) { if(!isprime[i]) prime[cnt++]=i; for(int j=0;j<cnt&&i*prime[j]<=maxn;j++) { isprime[i*prime[j]]=1; if(i%prime[j]==0) break; //注意这两句话的顺序 } }}int main(){ get(); cout<<cnt<<endl; printf("%d %d %d\n",prime[0],prime[1],prime[2]); return 0;}
素数筛选法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。