区间质数统计（加强版）

分发自HZK’s Blog（全平台分发）

本文标题：区间质数统计（加强版）

本文链接地址：https://blog.zekun.fun/2021/%e7%bc%96%e7%a8%8b/c-cpp/663/

题目描述

给定区间[L,R] ， 请计算区间中素数的个数。 其中2≤L≤R≤2×109，R−L≤1000000

输入

两个数L和R。

输出

只有一行，区间中素数的个数。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
int pri[10000];
typedef long long LL;
bool a[maxn];
int Eratosthenes_Sieve(int n, int pri[]) {
    for (int i = 2; i * i <= n; i++)
        if (a[i] == 0)
            for (int j = i << 1; j <= n; j += i)
                a[j] = 1;
    int cnt = 0;
    for (int i = 2; i <= n; i++)
        if (!a[i])
            pri[cnt++] = i;
    return cnt;
}
int main() {
    int cnt = Eratosthenes_Sieve(50000, pri);
    LL L, R;
    scanf("%lld %lld", &L, &R);
    memset(a, 0, sizeof(a));
    for (int i = 0; i < cnt; i++)
        for (LL j = max(2ll, (L - 1) / pri[i] + 1) * pri[i]; j <= R; j += pri[i])
            a[j - L] = 1;
    int ans = 0;
    for (LL i = L; i <= R; i++)
        if (a[i - L] == 0)
            ans++;
    printf("%d", ans);
    return 0;
}
           

本篇文章由一文多发平台ArtiPub自动发布