素数筛+埃筛模版

博主链接

普通的素数筛

#include<stdio.h>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e7+7;//求MAX范围内的素数
long long su[MAX],cnt;
bool isprime[MAX];
void prime()
{
    cnt=1;
    memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数
    isprime[0]=isprime[1]=0;//0和1不是素数
    for(long long i=2;i<=MAX;i++)
    {
        if(isprime[i])
            su[cnt++]=i;//保存素数i
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)
        {
            isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数
        }
    }
}
int main()
{
    prime();
    //for(long long i=1;i<cnt;i++)
     //   printf("%d  ",su[i]);
    return 0;
}

埃筛(线性筛)筛素数

int p[maxn], check[maxn], tot = 0;
void prime()
{
    check[1]=1;
    check[0]=1;
    for(int i=2;i<=n;i++)
    {
        if(!check[i])p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;j++)
        {
            check[i*p[j]]=1;
            if(!(i%p[j]))break;//*****关键
        }
    }
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 18:05
点赞 评论 收藏
分享
昨天 10:44
青岛工学院 Java
机械打工仔:对方没做错任何事,你自己在这自找没趣呢,就算他工资不高,人家定多少薪资是人家的事,况且人家写了1~3年清清楚楚
点赞 评论 收藏
分享
北漂的牛马人:211佬,包进的,可能是系统问题
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务