素数相关/线性筛法

判断素数:

int sushu(int x)
{
    if(x<=1)return 0;
    for(int i=2; i<=sqrt(x); i++)
        if(x%i==0)
            return 0;
    return 1;
}

线性筛法:

const int N=1000+7;
ll  prime[N]= {1};
int pcnt=0;
int factor[N]= {1,1};
void Init_Prime()
{
    pcnt=1;
    for(ll i=2; i<N; i++)
    {
        if(!factor[i])
        {
            prime[pcnt++]=i;
            factor[i]=i;
        }
        for(ll j=1; j<pcnt&&i*prime[j]<N; j++)
        {
            factor[i*prime[j]]=prime[j];
            if(!(i%prime[j]))
                break;
        }
    }
    return;
}

普通筛法:

const int N=2000100;
int isprime[N];
void init()
{
    int i,j;
    isprime[1]=1;
    for(i=2; i<=sqrt(N); i++)
    {
        if(!isprime[i])
        {
            for(j=i+i; j<=N; j+=i)
                isprime[j]=1;
        }
    }
}

哈理工模板:

#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 25600000;
bool a[N];
int p[N];
int n;
void Prime1()
{
    memset(a, 0, n * sizeof a[0]);
    int num = 0, i, j;
    for(i = 2; i < n; ++i) if(!a[i])
        {
            p[num++] = i;
            for(j = i+i; j < n; j +=i)
                a[j] = 1;
        }
}

void Prime2()
{
    memset(a, 0, n*sizeof a[0]);
    int num = 0, i, j;
    for(i = 2; i < n; ++i)
    {
        if(!(a[i])) p[num++] = i;
        for(j = 0; (j<num && i*p[j]<n); ++j)
        {
            a[i*p[j]] = 1;
            if(!(i%p[j])) break;
        }
    }
}
int main()
{
    n = 100;
    Prime2();
}

优化空间的线筛

for(int i=2; i<N; i++)
{
    if((isprime[i/32]&(1ll<<(i%32)))==0)
    {
        prime[tot++]=i;
    }
    for(int j=0; j<tot&&i*prime[j]<N; j++)
    {
        isprime[i*prime[j]/32]|=1<<(i*prime[j]%32);
        if(i%prime[j]==0)
            break;
    }
}

洛谷线筛:

#include <cstring>
#include<cstdio>
#include<iostream>//头文件
using namespace std;
long long prime[10000001],primesize;//prime[]表示素数，primesize表示素数个数 
bool isprime[10000001];//判断是否是质数 
void getlist(long long listsize)
{
    memset(isprime,1,sizeof(isprime));//将isprime赋初值 
    isprime[1]=false;//1既不是质数也不是合数所以赋初值为false 
    for(long long i=2;i<=listsize;i++)//listsize就是n，1被排除所以从2到n 
    {
        if(isprime[i])prime[++primesize]=i;//如果是就存下来 
         for(long long j=1;j<=primesize && i*prime[j]<=listsize;j++)//i*prime【j】肯定要数据范围内，所以《=n 
         {
            isprime[i*prime[j]]=false;//i*已知的所有素数定为合数 
            if(i%prime[j]==0)break;//避免多次筛，每个合数只被他最小的因子素数筛去 
        }
    }
}
int main()
{
    long long n,m,a;
    scanf("%lld%lld",&n,&m);//输入 
    getlist(n);//找出所有质数 
    for (int i=1;i<=m;++i) 
    {
        scanf("%lld",&a);//输入 
        if (isprime[a]!=false)//判断是否是质数 
        cout<<"Yes"<<endl;
           else cout<<"No"<<endl;
    }
    return 0; 
}