~素数数目~~~~区间筛法（埃氏筛法）

最新推荐文章于 2023-03-15 20:11:24 发布

Daowuu

最新推荐文章于 2023-03-15 20:11:24 发布

阅读量1k

点赞数 1

分类专栏：数论文章标签：算法

本文链接：https://blog.csdn.net/Long_hen/article/details/104506039

版权

数论专栏收录该内容

6 篇文章

订阅专栏

题目描述（这里可以点哦）

给定区间[L,R]，计算区间素数个数。
输入
输入两个整数L，R(1<=L<=R<=10^12,R-L<=1000000)
输出
输出一行表示区间素数的个数
样例输入 Copy
2 11
样例输出 Copy
5

素数个数问题，一般就是用埃氏筛法（复杂度O(nloglogn)），这题自然也不例外，具体思路如下：
第一步，用埃氏筛法得到1 ~ R^1/2之间的全部素数；
第二步，用第一步得到的素数表把区间 [ L,R ]中的所有合数筛去；
第三部，统计剩下的素数个数；

事实上第一步和第二步是放在一起进行的，代码如下：

#include<cstdio>

using namespace std;

typedef long long LL;
const int N = 1e6+1;

bool f[N], t[N];//需要筛两个区间

LL S_sieve(LL l,LL r){//区间筛法    
    int sum = 0;    //统计L~R内合数的个数
	for(LL i = 2; i * i <= r; ++ i){
		//筛选2~sqrt(r)之间的素数 
		if (f[i]) continue;
		for(LL j = i * i; i <= 1000 && j * j <= r; j += i){
			f[j] = true;
		}
		//用筛选出的质数筛去区间l~r的合数 
        LL s = (l + i - 1) / i;
		if (i > s) s = i;       //保守i*i 
		for(LL j = s * i; j <= r; j += i){
            if (t[j - l + 1]) continue;
			t[j - l + 1] = true;
            sum ++;
		}
	}	
    if (l == 1) sum ++; //排除1
    sum = r - l + 1 - sum; //得到质数个数
	return sum;
}

int main(){
    LL L, R;
	scanf("%lld%lld", &L, &R);
    printf("%lld", S_sieve(L, R));
	return 0;
}