題目描述
給定區(qū)間[L, R] ， 請計算區(qū)間中素數(shù)的個數(shù)镀虐。
數(shù)據(jù)規(guī)模和約定
2 < = L < = R < = 2147483647 R-L < = 1000000
輸入
兩個數(shù)L和R箱蟆。
輸出
一行，區(qū)間中素數(shù)的個數(shù)刮便。
樣例輸入
2 11
樣例輸出
5
提示
C語言在線學習平臺微信號dotcpp
來源
算法提高
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
const int maxn=1000001;
int prime[maxn],p[maxn],cnt;
bool res[maxn];
void findPrime(int m) //使用埃式素數(shù)篩法
{
for(int i=2;i<=m;i++)
{
if(p[i]==false) prime[++cnt]=i;
for(int j=i+i;j<=m;j+=i) p[j]=true;
}
}
int main(void)
{
int n,m;
cin>>n>>m;
findPrime((int)sqrt(m));
for(int i=1;i<=cnt;i++)//對cnt個包含 所有的 可能是區(qū)間[n,m]中 合數(shù)因子 的集合 進行枚舉
{
//cout<<prime[i]<<endl;
for(ll j=(n+prime[i]-1)/prime[i]*prime[i];j<=m;j+=prime[i])//把[n,m]中是素數(shù)表中素數(shù)至少為2倍的數(shù)標記
{
//j是區(qū)間[n,m]中第一個是素數(shù)prime[i]整數(shù)倍數(shù)的數(shù)值
if(j==prime[i]) continue;
else res[j-n]=true;
}
}
int count=0;
for(int i=0;i<=m-n;i++) if(res[i]==false) count++;
cout<<count;
return 0;
}
