エラトステネスのふるい ver 2

const int N_MAX = 1e7 + 10;
bool is_prime[N_MAX];

// エラトステネスのふるい
void Eratosthenes(){
    FOR(i, 0, N_MAX){
        is_prime[i] = true;
    }
    is_prime[0] = false;
    is_prime[1] = false;
    for(ll i=2; i*i<=N_MAX; i++){
        if(is_prime[i]){
            int p = i;
            int step_p = p;
            // それの倍数を消していく
            while(p < N_MAX){
                p += step_p;
                if(p<N_MAX){
                    is_prime[p] = 0;
                }
            }
        }
    }
}

• iはsqrt(N_MAX)まで回せば十分なのでそこを修正した
• 10⁷なら通る
• ACコード https://yukicoder.me/submissions/351323

篩を使う問題

• 上司のおごり http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202
  • 参考解法 DP&篩 http://ei1333.blogspot.com/2013/11/0202.html