判断素数

po出大佬原博客https://www.cnblogs.com/linyujun/p/5198832.html

大佬讲了各种写法，非常的详细，这里只写埃筛和线筛两种。

埃筛 复杂度O(nloglogn)

#include<bits/stdc++.h>
using namespace std;
const int N=10000+6;
bool prime[N];
void init()
{
    for(int i=2;i<N;i++) prime[i]=true;
    for(int i=2;i*i<N;i++)
    {
        if(prime[i])
        {
            for(int j=i*i;j<N;j+=i)
            {
                prime[j]=false;
            }
        }
    }
}
int main()
{
    init();
    return 0;
}

这是埃筛，主函数可经过自己需要去填写。

线筛 复杂度O(n)

#include<bits/stdc++.h>
using namespace std;
const int N=100000+6;
bool prime[N];//prime[i]表示i是不是质数
int p[N],tot=0;//P[N]用来储存质数
void init()
{
    for(int i=2;i<N;i++) prime[i]=true;
    for(int i=2;i<N;i++)
    {
        if(prime[i]) p[tot++]=i;//把质数存起来
        for(int j=0;j<tot&&i*p[j]<N;j++)
        {
            prime[i*p[j]]=false;
            if(i%p[j]==0) break;//保证每个合数被他最小的质因子筛去
        }
    }
}
int main()
{
    init();
    return 0;
}

线筛的写法要比埃筛复杂一些。