数学--数论--素数

定义判断：

代码语言：javascript复制

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

埃氏筛法

代码语言：javascript复制

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;
        }
    }
}

代码语言：javascript复制

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;
        }
    }
}

线筛（欧式筛）

代码语言：javascript复制

#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;
}

数学

0 人点赞