ABC084: D - 2017-like Number

競技プログラミング AtCoder 素数

問題

問題文

https://abc084.contest.atcoder.jp/tasks/abc084_d

問題概要

N も (N+1) / 2 も素数であるという条件を満たす奇数 N を 2017に似た数 とする。

{ Q (1 \leqq Q \leqq 10^{5})} 個のクエリが与えられ, 各クエリでは奇数 {l_i, r_i (1 \leqq l_i \leqq r_i \leqq 10^{5})} が与えられる。

区間 { [ l_i, r_i ] } で 2017に似た数となる奇数の個数を答えよ。

解答例

指針

  • まず素数を列挙し, ある区間までに存在する 2017 と似た数の累積和をとる。

解説

{l_i, r_i } の最大値 (105) を N, クエリの数 Q の最大値 (105) を M とする。

素数の列挙ができれば 2017 に似た数の累積和をとるのに O(N) , 各クエリの処理に O(M) かかるので全体の計算量は (素数列挙にかかる計算量) + O(N) + O(M) となる。

素数列挙を行う方法を幾つか述べる。

愚直な方針

0 ~ N まで素数判定を 1 つずつ行うことで素数列挙を行う。

素数列挙にかかる計算量は { O(N \sqrt{N}) } となる。

この場合, 全体の計算量は素数列挙にかかる時間が支配的となり { O(N \sqrt{N}) } となる。

/* Language: C++14 (GCC 5.4.1)
   time: 102 ms
   Memory: 1024 KB */

#include <cstdio>
#include <cstring>
#define MAX_N 100001

bool IsPrime[MAX_N + 1];

// 愚直な素数列挙
void get_primes() {
    IsPrime[0] = false; IsPrime[1] = false;
 
    for (int i = 2; i < MAX_N; i++) {
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0) { IsPrime[i] = false; }
        }
    }
}

int main() {
    int Q, l, r;
    int cnt[MAX_N + 1] = {0};

    memset(IsPrime, 1, sizeof(IsPrime));
    get_primes();

    for (int i = 3; i <= MAX_N; i += 2) {
        if (IsPrime[i] && IsPrime[(i+1)/2]) { cnt[i]++; }
    }
    // 2017 に似てる数の累積和をとっている
    for (int i = 1; i <= MAX_N; i++) {
        cnt[i] += cnt[i-1];
    }

    scanf("%d", &Q);

    while (Q--) {
        scanf("%d %d", &l, &r);
        printf("%d\n", cnt[r] - cnt[l-1]);
    }

    return 0;
}

エラトステネスの篩

エラトステネスの篩というアルゴリズムを使うと素数列挙をより高速に行える。

既知の素数の倍数を取り除くことで素数を列挙している。

素数列挙にかかる計算量は { O(N \log{\log{N}}) }

この場合も全体の計算量は素数列挙にかかる時間が支配的となり { O(N \log{\log{N}}) } となる。

/* Language: C++14 (GCC 5.4.1)
   time: 28 ms
   Memory: 1024 KB */

#include <cstdio>
#include <cstring>
#define MAX_N 100001

bool IsPrime[MAX_N + 1];

// エラトステネスの篩
void get_primes() {
    IsPrime[0] = false;
    IsPrime[1] = false;

    for (int i = 2; i*i <= MAX_N; i++) {
        if (IsPrime[i]) {
            for (int j = i*i; j <= MAX_N; j += i) {
                IsPrime[j]= false;
            }
        }
    }
}

int main() {
    int Q, l, r;
    int cnt[MAX_N + 1] = {0};

    memset(IsPrime, 1, sizeof(IsPrime));
    get_primes();

    for (int i = 3; i <= MAX_N; i += 2) {
        if (IsPrime[i] && IsPrime[(i+1)/2]) { cnt[i]++; }
    }

    for (int i = 1; i <= MAX_N; i++) {
        cnt[i] += cnt[i-1];
    }

    scanf("%d", &Q);

    while (Q--) {
        scanf("%d %d", &l, &r);
        printf("%d\n", cnt[r] - cnt[l-1]);
    }

    return 0;
}

アトキンの篩

エラトステネスの篩よりも高速なアルゴリズムとしてアトキンの篩がある。

原理はよく知らない。

素数列挙にかかる計算量は { O(N / \log{\log{N}}) }

全体の計算量は累積和をとるのにかかる時間が支配的となり { O(N) } となる。

アトキンの篩を使っても実行時間はほとんど変わらなかった。

素数列挙はエラトステネスを使えば十分でアトキンの篩を使わなければならない場面はほとんどなさそうである。[要出典]

/* Language: C++14 (GCC 5.4.1)
   time: 28 ms
   Memory: 1024 KB */

#include <cstdio>
#define MAX_N 100001
 
bool IsPrime[MAX_N + 1];
 
// アトキンの篩
void get_primes() {
    for (int x = 1; x*x < MAX_N; x++) {
        for (int y = 1; y*y < MAX_N; y++) {
            int n = (4*x*x) + (y*y);
            if (n <= MAX_N && (n % 12 == 1 || n % 12 == 5)) {
                IsPrime[n] ^= true;
            }
            n = (3*x*x)+(y*y);
            if (n <= MAX_N && n % 12 == 7) {
                IsPrime[n] ^= true;
            }
            n = (3*x*x)-(y*y);
            if (x > y && n <= MAX_N && n % 12 == 11) {
                IsPrime[n] ^= true;
            }
        }
    }
 
    for (int r = 5; r*r < MAX_N; r++) {
        if (IsPrime[r]) {
            for (int i = r*r; i < MAX_N; i += r*r) {
                IsPrime[i] = false;
            }
        }
    }
    IsPrime[2] = IsPrime[3] = true;
}
 
int main() {
    int Q, l, r;
    int cnt[MAX_N + 1] = {0};
 
    get_primes();
 
    for (int i = 3; i <= MAX_N; i += 2) {
        if (IsPrime[i] && IsPrime[(i+1)/2]) { cnt[i]++; }
    }
    for (int i = 1; i <= MAX_N; i++) {
        cnt[i] += cnt[i-1];
    }
 
    scanf("%d", &Q);
 
    while (Q--) {
        scanf("%d %d", &l, &r);
        printf("%d\n", cnt[r] - cnt[l-1]);
    }
 
    return 0;
}

参考文献