P1835 素数密度[二次筛法][数论]

P1835 素数密度

时间限制: 1.00s 内存限制: 128.00MB

复制 Markdown

中文

退出 IDE 模式

题目背景

UPD:

• 2024.8.12：加入一组 Hack 数据。

题目描述

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

1≤L≤R<231，R−L≤106。

输入格式

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

输出格式

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

输入输出样例

输入 #1复制运行

2 11

输出 #1复制运行

5

数据范围很大直接筛的话不现实

注意到每个合数都可以分解为若干个质数的乘积 并且一定有一个质数 小于等于sqrt(n) 那么我们可以筛出1到sqrt(n)的所有质数 然后表示这些质数在区间l到r的倍数为合数 剩下没有被标记的数字就是质数

代码实现如下：

#include <bits/stdc++.h> using namespace std; #define int long long vector<int>minp,primes; void sieve(int n){ minp.assign(n+1,0); primes.clear(); for(int i=2;i<=n;i++){ if(!minp[i]){ minp[i]=i; primes.push_back(i); } for(auto p:primes){ if(i*p>n)break; minp[i*p]=p; if(p==minp[i])break; } } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int l,r; cin>>l>>r; int cnt=0; sieve(50000); vector<bool>vis(r-l+1,0); for(auto p:primes){ for(int j=max(p*2,(l+p-1)/p*p);j<=r;j+=p){ vis[j-l]=1; } } for(int i=0;i<=r-l;i++){ if(l+i==1)continue; if(!vis[i])cnt++; } cout<<cnt<<'\n'; return 0; }