一.什么是素数
长话短说：
因数只有1和本身的正整数，（但素数不包含1）. 比如 2 ，3，5，7…
二.如何判断一个数是素数
用1中的定理，也就是说，如果某个大于1的正整数与任何小于等于它的正整数的最大公因数都是1，则为素数
咳咳咳…扯远了，我们的重心不在这里，重点在下面：
三.什么是素数筛
首先，给你一个区间的正整数，让你求在这段区间内有哪些素数？
这里，我们就可以用“
筛选的方法
”筛去不是素数的正整数（也就是合数）剩下的就是素数了，但不同的筛法效率也是不一样的
1. 最直接的筛法
获取1到n以内的所有素数
int prime[200000]={0},c=0; //存储素数的数组，数组里面素数的个数
void getPrime(int n)
{
prime[++c] = 2; //2肯定是素数
for(int i=3;i<=n;i+=2) //素数肯定是奇数,所以i = i+2
{
int flag = 0; //判断i是不是素数标记
for(int j=2;j*j<=i;++j) //判断i是不是还有其他因数
{
if(i%j==0) //如果i还有其他因数，则不是素数
{
flag = 1; //标志i不是素数
break; //退出对i判断的循环
}
}
//如果执行了上面代码flag还是0，说明i就是素数
if(!flag) prime[++c] = i;
}
}
这种方法甚至称不上是筛，压根就是暴力枚举。。复杂度O(n*sqrt（n））
评价：
基本上不推荐
2. 埃氏筛
又称为
埃拉托斯特尼筛法
，是一种比较古老的筛法，我们直接来看它的筛法原理
准备一个判断是否素数的数组
，
bool isPrime[20000];
初始化：假设 2 – n都是素数。（1不是，我们先排除）
for(int i=2;i<=n;++i)
isPrime[i] = true;
代码如下：
void getPrime(int n)
{
for(int i=2;i<=n;++i)
isPrime[i] = true; //假设2-n都是素数
for(int i=2;i<=n;++i) //遍历2-n里面所有数
if(isPrime[i]) //如果i是素数
//i是素数的话，那么i的倍数肯定就不是合适
//即 i*2，i*3 .....i*j肯定不是素数，注意边界i*j<=n
for(int j=i;i*j<=n;++j)
//n以内，且是i的倍数的数肯定不是素数，设为false
isPrime[i*j] = false;
}
这是一种比较古老的素数筛选法，时间复杂度O(n*log(logn))
评价：一般题目都可以使用
3. 欧拉筛（线性筛）
欧拉筛基本上是埃氏筛的优化升级版，为什么这么说？
我们来看一个问题：
比如我要筛选 1 – 20以内所有的素数，就以埃氏筛来完成
我们发现，每次筛出去一个素数的倍数时存在重复筛出的操作，比如 2 * 3,和3 *2，也就是说 6 是素数2的倍数也是素数3的倍数，我们筛了两次，这就重复做了无用功。所以，我们以此来寻求优化的算法方案，这时候我们再看看
欧拉筛
（也叫
线性筛
）
《1》
我们定义一个保存素数的数组
int prime[20000];
《2》
我们定义一个记录素数数组内素数个数整型
int c = 0;
《3》我们定义一个用来判断某个数是否已经被访问的数组
bool isVisit[20000]; //默认都是false
void EulerSevie(int n)
{
for(int i = 2;i <= n; ++i)//老规矩，遍历区间
{
if(isVisit[i] == false) //如果这个数未被访问，则是素数
prime[++c] = i; //将素数保存在素数数组里面，计数+1
//下面for循环及里面的语句才是这个算法的精髓，我们下面细讲
for(int j = 1;j <= c && i * prime[j] <= n; ++j)
{
isVisit[i * prime[j] ] = true;
if (i % prime[j] == 0)
break;
}
}
}
注意!!!,下面的图解有一点问题，在i=4的时候，由于4%2（素数）已经退出了第二层循环，所以不存在对4*3的visit赋值情况，而对4*3的visit情况赋值已经在i=6的时候对6*2赋值了true，因为6*2=3*4（感谢某大佬的指错）
-
（这是当i为素数的情况下）
欧拉每次得出素数的时候，再进入循环，根据此时素数数组的个数来筛选掉此时i的倍数，而且这个倍数一定是素数（由prime可以得知）
2.
（当i不是素数的时候）
此时的i一定被标记为true，也就是 i 之前的素数将其标记为true，这样子就避免了非素数 i 进入第一个if而被存储在素数数组里面（至于为什么被标记为true自己笔写一遍就晓得了，不多说）
3
.最后一步有一个（i % prime【j】==0） 首先此时的 i 不可能为素数，因为素数模其他素数不可能被整除，也就是说，这个i一定是合数，
4
.理解一下最后一个跳出循环，如果prime【j】是i的倍数的时候，也就是说
i = m * prime【j】， …①
假如没有这个break条件，则++j，也就是算到了
i * prime【j+1】这里了
把①式子带入下面式子可以知道此时为
m * prime【j】* prime【j+1】
结合欧拉筛的定理，其是根据最小素数因子进行筛选，也就是说prime【j】
是最小素数因子，如果不break的话，可能会出现埃氏筛那种重复操作的无用功，比如：
i = 9 的话，此时prime【1】=2，prime【2】=3，prime【3】=5，prime【4】=7；
本来是当 j=2 的时候跳出循环，但是却没有，那么j = 3
则 9 * 5 = 3 * 3 * 5 ，该统计在 i = 15 的时候也会统计，也就是当 i = 15 时候，j = 2 ，prime【2】 = 3，也统计了 3 * 15 = 9 *5 ，明显，重复统计，所以要及时break；
欧拉筛：
时间复杂度O（n），普遍使用的素数筛
评价：普遍使用
PS：至于数组定义多大，int还是long long int，完全取决于题目要求
本人讲的可能不好，实在是实力有限，O(∩_∩)O哈哈~，祝大家学业更上一层楼！！！
拿下面数论比赛练练手吧：
https://vjudge.net/contest/377796#problem/E