素数密度

题目背景

UPD:

• 2024.8.12：加入一组 Hack 数据。

题目描述

给定 $L,R$，请计算区间 $[L,R]$ 中素数的个数。

$1\le L\le R<2^{31}$，$R-L\le 10^6$。

输入格式

第一行，两个正整数 $L$ 和 $R$。

输出格式

一行，一个整数，表示区间中素数的个数。

样例 #1

样例输入 #1

2 11

样例输出 #1

5

题目分析：开始想到了欧拉筛法，但交上去发现wa只得了40分，了于是看数据范围发现然而我们并不能筛到 2e9,空间上也不允许，想想办法，因为2e9范围内的质数因子最大也到不了50000(用计算器或者代码sqrt一下2∼50000以内的素数，然后对于每一个数，筛出质因子的倍数，剩下的就是区间内的质数啦。

数学知识储备
【大于L,并且是p的倍数,最小整数是多少?】

#include <bits/stdc++.h>using namespace std;
typedef long long LL;int main() {//数学知识储备//【大于等于L,并且是p的倍数,最小整数是多少?】int p = 3;for (LL L = 100; L <= 200; L++)cout << max(2ll, (L - 1) / p + 1) * p << endl;return 0;
}

最后奉上代码部分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;int primes[N];//存储所有素数 
bool vis[N],a[N];//vis存储i是否被筛掉 
//数组a记录偏移后的数据是不是合数，1：合数；0：质数。a[i]表示l+i是不是合数, 有一个偏移量l
ll l,r; 
int cnt; void get_primes()
{cnt = 0;for(int i = 2; i <= 50000; i++){if(!vis[i]) primes[cnt++] = i;for(int j = 0; primes[j] <= 50000 / i; j++){vis[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}ll read()
{ll s=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*f;
}int main() {l = read(),r = read();l = l == 1 ? 2 : l;get_primes();for(int i = 0; i < cnt; i++){ll st = max(2ll,(l-1) / primes[i] + 1) * primes[i];for(ll j = st; j <= r; j += primes[i]) a[j - l] = true;}//区间范围,因为我们无法完全映射所有的区间，只能采用类似于偏移的办法对某段区间整体偏移l进行描述。int ans = 0;for (ll i = l; i <= r; i++) if (!a[i - l])ans++;printf("%d", ans);return 0;
}