1.质数的筛选

/** 质数的筛选：
* 1. Eratosthenes 筛法 O(N * loglogN)
*/
void primes(int n){
    memset(v, 0, sizeof(v)); //
    for(int i = 2; i <= n; ++ i){
        if(v[i]) continue;
        cout << i << endl; //
        for(int j = i; j <= n / i; ++ j) v[i * j] = 1;
    }
}


/**
* 2. 线性筛法 O(N)
* v[i]记录了i的最小质因子
*/
int v[maxn], prime[maxn];
void primes(int n){
    memset(v, 0, sizeof(v));
    m = 0;
    for(int i = 2; i <= n; ++ i){
        if(v[i] == 0) { v[i] = i; prime[++ m] = i; }
        for(int j = 1; j <= m; ++ j) {
            if(prime[j] > v[i] || prime[j] > n / i) break;
            v[i * prime[j]] = prime[j];
        }
    }
    for(int i = 1; i <= m; ++ i) cout << prime[i] << endl;
}