题解 | #素数的个数#
素数的个数
https://ac.nowcoder.com/acm/problem/235228
R-L<=10的6次方，则开一个10的6次方的数组，对于每一个素数都减去L存入数组，1~20亿中大概有近一亿个素数，用欧拉筛也不可能完成，所以只能在L,R区间内判断，一个一个求明显会TLE。
所以转换思路，利用两层循环i*j来求出L,R内有质因子的数，乘出来的数一定是质数，直接排除。
#include<iostream>
using namespace std;
const int N=1e6+10;
int n,l,r;
int primes[N];
int cnt=0;
int main()
{
cin>>l>>r;
for(int i=2;i<=r/i;i++)
{
for(int j=r/i;j>=2;j--)
{
if(i*j<l) break;
else
{
primes[i*j-l]=1;
}
}
}
for(int i=l;i<=r;i++)
{
if(!primes[i-l])
cnt++;
}
cout<<cnt<<endl;
return 0;
}
海康威视公司氛围 461人发布
