#include<bits/stdc++.h> using namespace std; bool prime[2000009]; int main(){ int l,r; cin>>l>>r; int ans=0; prime[1]=1; for(int i=2;ii<=r;i++){ if(!prime[i]){ for(int j=2i;j<=r;j+=i){ prime[j]=1; } } } for(int i=l;i<=r;i++){ if(!prime[i]){ ans++; } } cout<<ans; return 0; }

AC代码，159msAC代码，159msAC代码，159ms

知识点！！！ 线性筛（) 维护布尔型数组 isPrime 储存每个数是否为质数 前缀和（可以不用） 维护整型数组 pre，i 项储存前 i 个数字中有几个质数 两个算法加起来时间复杂度 O(n)，9ms过 代码如下：

#include <iostream> #include <cmath> using namespace std; int check(int n) { if (n1) return 0; for (int i=2;i*i<=n;i++) if (n%i0) return 0; return 1; } int main() { int n,m; cin>>n>>m; int sum=0; for(int i=n;i<=m;i++) { if (check(i)) sum++; } cout<<sum; return 0; }