『算法-ACM 竞赛-数学-数论』素数

ACM 常用模板合集

定义判断：

bool isPrime (int n)
{
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) return false;
	}
	else return false;
}

埃氏筛法

int primes[N],cnt;
bool bprime[N];
void getPrime(int n){
    memset(bprime,false,sizeof(bprime));
    bprime[0]=true;
    bprime[1]=true;

    for(int i=2;i<=n;i++){
        if(!bprime[i]){
            prime[cnt++]=i;
            for(LL j=i*2;j<=n;j+=i)
                bprime[j]=true;
        }
    }
}

int primes[N],cnt;
bool bPrime[N];
void getPrimes(int n){
    memset(bPrime,false,sizeof(bPrime));

    for(int i=2;i<=n;i++){
        if(!bPrime[i])
            primes[cnt++]=i;

        for(int j=0;j<cnt&&i*primes[j]<n;j++){
            bPrime[i*primes[j]]=true;
            if(i%primes[j]==0)
                break;
        }
    }
}

线筛（欧式筛）

#include<iostream>
#include<bitset>
using namespace std;
bitset<100000010>v;
int prime[6000001];
int m=0;
void primes(int n)
{
    for(int i=2; i*i<=n; i++)
    {
        if(!v[i])
        {
            for(int j=i*i; j<=n; j+=i)
                v[j]=1;
        }
    }
    for(int i=2; i<=n; i++)
        if(!v[i])
            prime[m++]=i;
    for(int i=0; i<m; i++)
        cout<<prime[i]<<endl;
}
int main()
{
    primes(1e3+20);
    return 0;
}