欧拉线性筛

埃氏筛写多了总会想：能不能让每个合数只被筛一次。我纠结了半天，最后记下了欧拉线性筛——每个合数只被它的最小质因子筛掉，复杂度压到 O(n)。模板贴在这里备查。

算法模板

vector<bool> is_prime(N, true);
vector<int> primes;

void get() {
    is_prime[0] = is_prime[1] = false;
    fer(i, 2, N + 1) {
        if(is_prime[i]) primes.push_back(i);
        for(int j = 0; j < primes.size() && primes[j] * i <= N; ++j) {
            is_prime[primes[j] * i] = false;
            if(i % primes[j] == 0) break;
        }
    }
}