题解 1525: 蓝桥杯算法提高VIP-找素数

解题思路:

题目要我们筛出L-R范围内的素数,那么我们只要将这个区间中的合数踢出去不就结束了吗

说起判断合数,我就想到了美猴王合数的一个性质:可以分解为两个不为1且不等于本身的因子相乘 即 n=a*b(n为合数).下证之:

设a<=b 则a * a<a*b

又因a* b=n,则a* a<=n*n

即a<=根号n

因此,在1-根号n的范围之中我们必能找到n的一个质因子

所以,我们只需要在1-根号R范围中筛出所有的质数(剩下的即为合数),然后用我们已经筛出来的因子去在L-R的范围中求出所有的合数,剩下来的即为我们要找的质数,而R的最大值大约为20亿,所以我们只用求(1-50000中的质数就可以拿他们来使用了!)

1.筛出1-50000中的所有质数,并且对合数打上标记.

2.在L-R的范围呢用我们已求出的质数筛出其中的合数(设p为质数,则i*p一定不为质数),并对其打上标记

3.遍历L-R,没有打标记的元素即为我们所求的素数

注意事项:

参考代码:

#include <bits/stdc++.h>

typedef long long LL;

using namespace std;

int prime[100001];

bool vis[1000010];

int oul(int n,int a[]){//欧拉筛筛出素数

for(int i=2;i<=n;i++){

if(!vis[i]){

vis[i]=1;

prime[++prime[0]]=i;//用prime[0]记录素数个数，从prime[1]开始存储素数

}
for(int j=1;j<=prime[0]&&i*prime[j];j++){

vis[i*prime[j]]=1;

if(i%prime[j]==0) break;

}
return prime[0];
}
int main()
{
memset(prime,0,sizeof(prime));

int cnt=oul(50000,prime);

LL L,R;

cin>L>>R;

L=L==1?2:L;//特判L=1时，将L赋值为2，因为1不是素数。如果不这样，下面会算入1为素数

memset(vis,0,sizeof(vis));//初始化数组

for(int i=1;i<=cnt;i++){

for(LL j=max((LL)2,(L-1)/prime[i]+1)*prime[i];j<=R;j+=prime[i]){//j的初始值是为了找到开始筛的数字

vis[j-L]=1;//我们从大于L的最小的能被prime[i]整除的数开始,标记合数

}
}
int ans=0;

for(LL i=L;i<=R;i++){

if(vis[i-L]==0) ans++;//剩下没有赋值为1的即为素数，计算素数个数

}
cout<<ans;

return 0;
}