luogu 1865 数论 线性素数筛法

#洛谷 1865 数论 线性素数筛法

最基本的线性素数筛法，当做复习欧拉筛法了，没有尝试过使用更暴力的筛法。。。

WA了一次，手抖没打\n

传送门 (https://www.luogu.org/problem/show?pid=1865)

#include <cstdio>

#include <cstring>

#include <algorithm>

const int maxn = 1000000 + 500;

int prime[maxn];

int isp[maxn];

int n, m;

int sum[maxn];

int l, r;

int tot = 0;

int main () {

    scanf("%d %d", &n, &m);

    for (int i = 2; i <= m; i++) isp[i] = 1;

    for (int i = 2; i <= m; i++) {

        if (isp[i]) {

            tot++;

            prime[tot] = i;

        }

        long long k;

        for (int j = 1; j <= tot && (k = 1ll * i * prime[j]) <= m; j++) {

            isp[k] = 0;

            if (!(i % prime[j])) break;

        }

    }

    for (int i = 2; i <= m; i++) sum[i] = sum[i-1] + (isp[i]);

    for (int i = 1; i <= n; i++) {

        scanf("%d %d", &l, &r);

        if (l < 1 || r > m) {

            printf("Crossing the line\n");

            continue;

        }

        printf("%d\n", sum[r] - sum[l-1]);

    }

    return 0;

}