14941 호기심

누적합으로 구간합 구하면 된다. 대신 시작을 어디서 하냐에 따라서 결과가 두 종류로 나눠지기 때문에

홀수항에서 시작하는 배열과 짝수항에서 시작하는 배열을 만든다.

#include <stdio.h>
using namespace std;
 
typedef long long ll;
int p[100001], ind[100001], cnt, d[2][100001];
 
int main() {
    ind[2] = ++cnt;
    p[2] = 2;
    for (ll i = 3; i < 100000; i += 2) {
        if (p[i]) continue;
        p[i] = 2;
        ind[i] = ++cnt;
        for (ll j = i * i; j < 100000; j += 2 * i)
            p[j] = 1;
    }
    
    for (int i = 1, flag = 1; i <= 100000; i++) {
        if (!ind[i]) ind[i] = ind[i - 1];
        d[0][i] = d[0][i - 1]; d[1][i] = d[1][i - 1];
        if (p[i] == 2) {
            d[1 - flag][i] += i * 3;
            d[flag][i] -= i;
            flag = 1 - flag;
        }
    }
    int n, a, b, flag;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &a, &b);
        if (p[a] == 2) a--;
        flag = ind[a] % 2;
        printf("%d\n", d[flag][b] - d[flag][a]);
    }
    return 0;
}