欧拉筛

定义

欧拉筛是一种用于求素数的高效筛法，时间复杂度为O(n)。
核心思想：每个合数都可以被表示为：n = min_prime * k(k ≥ min_prime)

实现

constexpr int N = 100010;  
vector<int> primes;  
bitset<N> is_not_prime;  
void eular(const int& n)  
{  
    for (int i = 2; i <= n; i++)  
    {  
        if (!is_not_prime[i])  
            primes.push_back(i); //不是素数则添加到primes中  
        for (const int& prime : primes) //筛出从i*2到i*最后一个素数的合数  
        {  
            if (i * prime > n)  
                break; //超出筛选范围就没有必要再筛了  
            is_not_prime[i * prime] = true; //标记（合数=最小质因数*另一个数）为非素数  
            if (i % prime == 0) //若真则i=prime（最小质因数）*另一个数（大于等于prime） 
                break; //接下来的Prime都比现在的prime大，  
                       //若继续循环则接下来的合数为（i*Prime=另一个数*Prime*prime）  
                       //此数应在I=另一个数*Prime时被I*prime标记而不是现在  
        }  
    }  
}