首页 > 其他 > 详细

素数筛选法

时间:2016-09-11 22:38:10      阅读:197      评论:0      收藏: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=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;
}

 

素数筛选法

原文:http://www.cnblogs.com/Ritchie/p/5862824.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!