区间筛

小沐202620 · 2021-09-12 22:51:41 · 个人记录

埃氏筛的变形

经典模板题

P1835 素数密度

#include<bits/stdc++.h>
using namespace std;
bool a[1000010];
int n, pri[10000];
int Eratosthenes_Sieve(int n, int pri[])//寻找n以内的质数,
                                       //a[i] = 0为质数
{
    int cnt = 0;
    for(int i = 2; i * i <= n; i++)
        if(a[i] == 0)//找到质数
            for(int j = i << 1; j <= n; j += i)
                a[j] = 1;
    for(int i = 2; i <= n; i++)
        if(!a[i]) pri[cnt++] = i;
    return cnt;
}
int main()
{
    int cnt = Eratosthenes_Sieve(50000, pri);
    long long l, r;
    scanf("%lld %lld", &l, &r);
    memset(a, 0, sizeof(a));
    for(int i = 0; i < cnt; i++)
        for(long long j = max(2ll, (l - 1) / pri[i] + 1) * pri[i]; j <= r; j +=pri[i])
            a[j - l] = 1;
    int ans = 0;
    a[1] = 1;
    for(long long i = l; i <= r; i++)
        if(!a[i-l]) ans++;
    printf("%d", ans = l == 2 ? ans + 1 : ans);//特判l = 2 否则ans会少1
    return 0;
}