2019-03-21 [蓝桥杯][算法提高VIP]找素数

题目描述
给定区间[L, R] ， 请计算区间中素数的个数。

数据规模和约定
2 < = L < = R < = 2147483647 R-L < = 1000000
输入
两个数L和R。
输出
一行，区间中素数的个数。
样例输入
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) //使用埃式素数筛法 
{
    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个包含 所有的 可能是区间[n,m]中 合数因子 的集合 进行枚举 
    {
        //cout<<prime[i]<<endl;
        for(ll j=(n+prime[i]-1)/prime[i]*prime[i];j<=m;j+=prime[i])//把[n,m]中是素数表中素数至少为2倍的数标记 
        {
            //j是区间[n,m]中第一个是素数prime[i]整数倍数的数值
            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;
}