数论--素数

欧拉筛法

每个合数仅被它的最小质因数筛去

bool prime[maxn];     //是否是素数
vector<int> v;        //素数表

void Euler(int n)
{
    mem(prime,1);
    for(int i = 2; i <= n; i++)
    {
        if(prime[i]) v.push_back(i);
        for(auto j : v)
        {
            if(i*j > n) break;
            prime[i*j] = 0;
            if(i%j == 0) break;
        }
    }
}