蓝桥杯算法提高VIP-找素数 （C++代码）

#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;
}

解题思路:

注意事项:

参考代码: