埃氏筛法

埃氏筛

一种求质数的高级算法

代码

#include<bits/stdc++.h>
using namespace std;

int n=1000;
vector<bool> isPrime(n,true);
void isPrime_func()
{
    for(int i=2; i*i<n; i++)
    {
        if(isPrime[i])
        {
            for(int j=i*i; j<n; j+=i)
            {
                isPrime[j]=false;
            }
        }
    }
}

int main()
{
    isPrime_func();
    cout<<isPrime[17]<<endl;
    return 0;
}