文章目录
- 前言
- 代码
- 思路
前言
有点儿难，至少对我来说。去年考试我没写出来。
代码
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>//加 math 那个头文件好像要加这个头文件，我之前编译错误过，血泪教训
#include<math.h>
#define N 1000010
#define LL long long
bool is_prime[N];//存 1 到 10^6 的数字是不是素数
bool is_prime1[N];//存映射之后的 r-l 区间的数字是不是素数，false 表示不是素数，true 表示是素数
void Eratosthenes(int n) {//这个是复制的埃氏筛法的模板is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i) is_prime[i] = true;for (int i = 2; i <= n; ++i) {if (is_prime[i]) {//prime.push_back(i);这个不要用，我就注释掉了，因为这里用数组 is_prime 数组的下标表示这个数字是啥就行了if ((long long)i * i > n) continue;for (int j = i * i; j <= n; j += i)// 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i// 的倍数开始，提高了运行速度is_prime[j] = false; // 是 i 的倍数的均不是素数}}
}
int get_ans(LL l,LL r){int max_prime=sqrt(r)+10;//这里是算最大的可能的因子，也不是最大的因子，就是那个试除法求因子 i*i<=n 的那个意思//避免掉边界问题，所以扩大了一些，向上取整或者加1都行，//但是不加的话，可能会出现一些问题，因为 sqrt 之后强制转换可能//有一些精度损失Eratosthenes(max_prime);//求素数因子for(int i=0;i<=r-l;i++){//假设最开始的时候区间里面全是素数is_prime1[i]=true;//假设开始的时候，映射之后的 [l,r] 这个区间，全是素数，注意 [l,r] 有 r-l+1 个数字}//比如[1,3] 有三个数字 3-1+1=3for(long long i=0;i<max_prime;i++){//这里遍历的是因子if(is_prime[i]){//只需要用素数因子，博客里面说了原因LL st=(l/i)*i;//求的是这个素数因子的在 l 右边的最小的倍数，st 是 start 的简写，这里比较复杂，下面博客里面会详细解释一下if(st<l){//让这个起点出现在 l 的右边st+=i;}if(st==i){//防止把素数给筛掉了st+=i;}for(long long j=st;j<=r;j+=i){//把素数因子的倍数筛掉is_prime1[j-l]=false;}}}int cnt=0;for(int i=0;i<=r-l;i++){//把 [l,r] 这个区间的数字映射到 [0,r-l] ，都是 r-l+1 个数字if(is_prime1[i]&&(l+i)>1){//(l+i)>1 的意思是只有 >=2 才有可能是素数cnt++;}}return cnt;
}
int main(){int t;scanf("%d",&t);while(t--){LL l,r;scanf("%lld%lld",&l,&r);int ans=get_ans(l,r);printf("%d\n",ans);}return 0;
}
思路
埃氏筛法，来自 oi-wiki
vector<int> prime;
bool is_prime[N];void Eratosthenes(int n) {is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i) is_prime[i] = true;for (int i = 2; i <= n; ++i) {if (is_prime[i]) {prime.push_back(i);if ((long long)i * i > n) continue;for (int j = i * i; j <= n; j += i)// 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i// 的倍数开始，提高了运行速度is_prime[j] = false; // 是 i 的倍数的均不是素数}}
}
时间复杂度是 O(n log log n) ，差不多就是线性的了，不过我学过线性筛之后没用过这个了，奥不对，其实是筛法我都没咋用过。
有一点需要说明，就是任何一个非素数数字可以被表示成若干个素数的乘积，这个结论非常重要，请记住这句话再往下看。假设我们直接用埃氏筛法和前缀和处理该题，因为 l 和 r 的数据范围是 10^9 ，哪怕时间复杂度是线性的，都超过了我们需要的 10^7 ，题干里面说 r-l<=10^6 ，那么对于这个区间我们用线性的做法是可以的。对于质数类型的题，有一个试除法求因子，也就是 i*i<=n ，我们枚举出 sqrt(n) 就能找到 n 的所有的因子，时间复杂度是根号的，10^9 开根号，这个时间复杂度我们是可以接受的。所以我们要想办法把 [l,r] 这个区间的数字的素数因子找到，然后用素数因子筛一遍这个区间的数字，就能找到这个区间的素数了。
这个 [l,r] 区间的因子只有素数因子是有意义的。因为非素数因子，可以拆解成更小的素数因子的乘积。（请看上一段第一句话）。那么 [l,r] 这个区间需要找到的最大的素数因子只要控制在 sqrt r 之内就可以了，用试除法找因子，相当于筛两遍。第一遍筛素数因子，第二遍用素数因子筛 [l,r] 区间的 r-l+1 个数字。
还有注意一下，两个数字都是 10^9 ，稍微乘一个数字，都可能爆 int ，所以这里用了 long long
