NOIP考点-埃氏筛法&&欧拉筛法
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
#include
#include
#include
#include
using namespace std;
bool prime[20000010];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
memset(prime,1,sizeof(prime));
prime[0]=prime[1]=0;
for(int i=2;i<=n;i++)
{
if(prime[i])
{
for(int j=i+i;j<=n;j+=i)
{
prime[j]=0;
}
}
}
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
if(prime[x])
{
printf("Yesn");
}
else
{
printf("Non");
}
}
return 0;
}
复杂度nlogn，但显然埃氏筛法对于比较大的范围，比如10^9这样的数显然是不可行的，所以我们需要学习另一种方法。
欧拉筛法：首先，我们知道当一个数为素数的时候，它的倍数肯定不是素数。所以我们可以从2开始通过乘积筛掉所有的合数。 将所有合数标记，保证不被重复筛除，时间复杂度为O（n）。代码比较简单↓_↓
/*求小于等于n的素数的个数*/
#include
#include
using namespace std;
int main()
{
int n, cnt = 0;
int prime[100001];//存素数
bool vis[100001];//保证不做素数的倍数
scanf("%d", &n);
memset(vis, false, sizeof(vis));//初始化
memset(prime, 0, sizeof(prime));
for(int i = 2; i <= n; i++)
{
if(!vis[i])//不是目前找到的素数的倍数
prime[cnt++] = i;//找到素数~
for(int j = 0; j<="n;" j++)<="" p="">
{
vis[i*prime[j]] = true;//找到的素数的倍数不访问
if(i % prime[j] == 0) break;//关键！！！！
}
}
printf("%dn", cnt);
return 0;
}
if(i % prime[j] == 0) break;←_←这一步比较难理解
解释：
首先，任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。
当i是prime[j]的整数倍时（i % prime[j] == 0），i*prime[j+1]肯定被筛过，跳出循环。
因为i可以看做prime[j]*某个数， i*prime[j+1]就可以看做 prime[j]*某个数*prime[j+1] 。而 prime[j] 必定小于 prime[j+1]，所以 i*prime[j+1] 必定已经被 prime[j]*某个数 筛掉，就不用再做了√
同时我们可以发现在满足程序里的两个条件的时候，prime[j]必定是prime[j]*i的最小质因子。这个性质在某些题里可以用到。
这样就可以在线性时间内找到素数了！
--end--
声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com
