求解
2024-08-02 16:37:02
发布于：北京
9阅读
0回复
0点赞
题目描述
给出两个整数
l
,
r
l,r,你需要求出
[
l
,
r
]
[l,r] 中素数的个数.
输入格式
输入一行，包含两个整数
l
,
r
(
1
≤
l
≤
r
<
2
31
,
r
−
l
≤
1
0
6
)
l,r(1≤l≤r<2
31
,r−l≤10
6
)。
输出格式
输出一行，包含一个整数。
输入输出样例
输入#1
复制
2 5
输出#1
复制
3
说明/提示
样例一解释:
2
∼
5
2∼5 里有
3
3 个素数
2
,
3
,
5
2,3,5
全部评论 1
这道啊，我照着老师的代码抄的（注释没抄全）：
#include <bits/stdc++.h> using namespace std; bool p[1000002];//标记i+l是否为素数 int main(){ long long n,m,cnt; cin>>n>>m; if(n==1)n++;//1非素数 for(int i = 2;i<=100000;i++){//枚举i，删i的倍数 long long low=(n-1)/i*i; low+=i; if(low==i)low+=i; for(int j = low;j<=m;j+=i){ p[j-n]=true; } } for(long long i = n;i<=m;i++){ if(!p[i-n])cnt++; } cout<<cnt; return 0; }2024-08-02 来自 广东
0
有帮助，赞一个