素数判定と累積和のアルゴリズムの練習です。 ABC084-D(https://beta.atcoder.jp/contests/abc084/tasks/abc084_d) の解答

ruisekiwa.md

累積和とは

ある区間内にある条件を満たすデータの数を出すために、あらかじめ最初からの和を取っておいて後で差を求める、というもの。 n番目までの和をSnと表す時、a番目からb番目までのデータの数はSb - Sa-1と表せる。 （SnはSn-1にn番目のデータの数を加えたものなので、最後は-1）

ruisekiwa_sample.cpp

#include <cstdio>
#include <cmath>
using namespace std;

#define REP(i, N) for(int (i) = 0; (i) < (N); i++)
#define MAX 1 << 20

bool isPrime(int n){
    if(n <= 1) return false;
    if(n == 2) return true;
    for(int i = 2; i*i <= n; i++)
        if(n % i == 0) return false;

    return true;
}

int main(){
    int n, a[50001], ans[100000];
    scanf("%d", &n);

    a[0] = 0;
    REP(i, 50000){
        int p = i*2+1;
        a[i+1] = a[i] + (isPrime(p) && isPrime((p+1)/2) ? 1 : 0);
    }

    int li, ri; 
    REP(i, n){
        scanf("%d %d", &li, &ri);
        ri = (ri+1)/2;
        li = (li+1)/2;
        ans[i] = a[ri] - a[li-1];
    }
    REP(i, n)
        printf("%d\n", ans[i]);
    return 0;
}