埃拉托斯特尼筛法+细节证明

本文主要是介绍埃拉托斯特尼筛法+细节证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

埃拉托斯特尼筛法

顾名思义就是筛素数的方法
首先埃拉托斯特尼筛法实基于这样一个定理：一个正合数n，一定存在小于sqrt(n)的素数因子

所以此筛法就是将n的所有小于等于sqrt(n)的素数因子圈出来，然后把他们的倍数划去，剩下的没有被划去的就是素数

例如：25，sqrt(25)=5,那么所有小于等于5的素数因子就是2，3，5
我们把2，3，5的所有倍数划去，也就是4，6，8，9，10，12，14，15，16，18，20，21，22，24，25，最后剩下2，3，5，7，11，13，17，19，23就是素数

实现代码如下:

/*埃拉托斯特尼筛法,原理一个合数一定有小于等于sqrt(n)的素因子，
把所有这些素因子的倍数全部划去，那么剩下的就全是素数了*/
#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e7;
bool vis[Maxn];
int prime[1000005];
int main()
{int n;cin>>n;prime[0]=0;memset(vis,false,sizeof(vis));for(int i=2;i<=sqrt(n);i++){if(!vis[i]){vis[i]=true;prime[++prime[0]]=i;for(int j=i*i;j<=n;j+=i){vis[j]=true;}}}for(int i=sqrt(n)+1;i<=n;i++){if(!vis[i]){prime[++prime[0]]=i;}}for(int i=1;i<=prime[0];i++) cout<<prime[i]<<endl;
}

这里我们对划去素数倍数的步骤进行了一些优化，也就是代码中的
for(int j=i*i;j<=n;j+=i)部分，我们并不是从1倍开始划，而是从i倍开始，
举个例子：假设素数i=5，那么我们直接从5×5开始划，而5×4，5×3，5×2…后面的就已经省略掉，因为这些已经被之前更小的素数的倍数筛过了，严谨的读者会怀疑，你怎么知道？别急，我们下面来证明

证明：
我们假设素数的倍数为i×p，其中p<i

情况1.当p是素数时，i×p这个数是素数p的倍数，已经被p筛除了

情况2.当p是合数时，由质因数分解我们知道，任何一个大于1的正整数可以表示为若干个素数的乘积，我们不妨假设p=A×B×C，因为A,B,C<p<i，所以A,B,C是小于i的素数，所以i×p这个数已经被A,B,C中其中一个素数筛除过了，到底是哪个素数筛除的，取决于谁最小，证毕！