エラトステネスのふるい

const int N_MAX = 10010;
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(i, 2, N_MAX){
        if(is_prime[i]==1){
            int p = i;
            int step_p = p;
            // それの倍数を消していく
            while(p < N_MAX){
                p += step_p;
                if(p<N_MAX){
                    is_prime[p] = 0;
                }
            }
        }
    }
}

素数の割合

  • N=10000のとき1200ほど
  • N=100000のとき9500ほど
  • ということで10%くらいで見ておけばいい

今回の問題の計算量

  • N = 10000
  • それぞれに対して素数リストでforをするので、
    • 計算量は10000 x 1000 = 107
    • よって間に合う

どこまで作れる?

  • 素数20万個なら制限時間内で作れる
  • その時にforで回す整数は270万ほど
const int M = 2750131;
int P[200000];
int invP[M + 1];
int minP[M + 1];
bool isP[M + 1];

void Eratosthenes() {
    int p = 0;
    REP(i, M + 1) isP[i] = true, minP[i] = -1;
    isP[0] = isP[1] = false;
    minP[0] = 0; minP[1] = 1;
    FOR(i, 2, M + 1) {
        if (isP[i]) {
            minP[i] = i;
            P[p] = i;
            invP[i] = p++;
            for (int j = i * 2; j < M; j += i) {
                isP[j] = false;
                if (minP[j] == -1) minP[j] = i;
            }
        }
    }
}