題目描述
給定區(qū)間[L, R] ， 請(qǐng)計(jì)算區(qū)間中素?cái)?shù)的個(gè)數(shù)。

數(shù)據(jù)規(guī)模和約定
2 < = L < = R < = 2147483647 R-L < = 1000000
輸入
兩個(gè)數(shù)L和R。
輸出
一行，區(qū)間中素?cái)?shù)的個(gè)數(shù)。
樣例輸入
2 11
樣例輸出
5
提示
C語(yǔ)言在線學(xué)習(xí)平臺(tái)微信號(hào)dotcpp
來(lái)源
算法提高

#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) //使用埃式素?cái)?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++)//對(duì)cnt個(gè)包含 所有的 可能是區(qū)間[n,m]中 合數(shù)因子 的集合 進(jìn)行枚舉 
    {
        //cout<<prime[i]<<endl;
        for(ll j=(n+prime[i]-1)/prime[i]*prime[i];j<=m;j+=prime[i])//把[n,m]中是素?cái)?shù)表中素?cái)?shù)至少為2倍的數(shù)標(biāo)記 
        {
            //j是區(qū)間[n,m]中第一個(gè)是素?cái)?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;
}