质数定义
一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。
由此定义我们便得到第一种判断质数的方法。
试除法判断质数
试除法是根据质数定义直接得到的判断质数的方法。
bool is_prime(int x) { if (x < 2) //质数均大于1，即小于2 return false; for (int i = 2; i <= x ; i ++ ) if (x % i == 0)//一旦有因子，就不是质数了 return false; return true;//全部遍历一遍没有发现因子，即为质数 }
那正能不能进一步优化呢？
设i为n的约数，则i/n也为n的约数
如
n=12 i=2 => n/i=6 2是12的约数，6也是12的约数。 i=3 => n/i=4 3是12的约数，4也是12的约数。
所以n当中的约数都是成对出现的，我们只需枚举一对当中较小的那一个。
即枚举的数满足i<=n/i
整理
i<=n/i i*i<=n i<=sqrt(n)
所以只需枚举到sqrt（n）即可。
方案选择
1.i
2.sqrt(n)【不推荐，需要不断调用函数math.h】
3.i*i
于是我们就得到了第一个模板。
模板
bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) return false; return true; }
试除法分解质因数
分解质因数也是常见题型，
也同样可以用试除法解决。
根据算术基本定理，不考虑排列顺序的情况下，
每个正整数都能够以唯一的方式表示成它的质因数的乘积。
比如一个数16 在分解时先找到2这个质因子，然后由于16/2后还可以/2，所以会在2这个质因子上产生次方。
不优化版本：
从2~n 找到能整除的因子然后算次方。
由此我们可以写出代码。
void divide(int x) { for (int i = 2; i <= x ; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } cout << endl; }
那优化版本呢？
这时我们就又需要知道另一个定理：
n中最多仅包含一个大于根号n的质数。
其实也很容易得证 sqrt（n）*sqrt（n）=n ，如果两因子都大于 sqrt（n），乘积就不是n了。
所以就得出质因数分解的模板。
模板
void divide(int x) { for (int i = 2; i <= x / i; i ++ )//先枚举小于根号x的素数 if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl;// cout << endl; }
埃氏筛法（朴素筛）
题中的数据范围是10的六次方，部分题目的上限甚至达到10的八次方，
这时简单的试除法作答肯定会超时。
所以下面介绍一种筛法
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法
埃氏筛法时间复杂度是O(n*lglgn)。
简单的说就是先从指定范围内开始遍历，并在遍历过程中删除遍历过的元素的倍数，剩下的即为素数。
例如
在筛质数时，我们会发现，
筛去2后，2的倍数4、6、8等一定不是素数;
筛去3后，3的倍数6、9、12等一定不是素数。
这样就不需要再判断2和3的倍数了。
证明：
设p是素数。
元素p没有被删掉，则说明它不是2~p-1间任何一个数的倍数，即2~p-1之间没有p的约数，故p为素数。
模板
void get_primes1(){ for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉； } } }
那还能不能更快呢.
欧拉筛法（线性筛）
线性筛法-O(n), n = 1e7的时候基本就比埃式筛法快一倍了。
原理
在遍历过程中通过从小到大枚举存放素数数组里面的素数来找出合数pj*i的最小质因数pj，最后通过最小质因子pj将全部合数删除。
证明
算法核心：x仅会被其最小质因子筛去，因为仅筛一次所以时间复杂度是O（n），故被成为线性筛。
模板
void get_prime(int x) { for(int i = 2; i <= x; i++) { if(!st[i]) prime[cnt++] = i; for(int j = 0; prime[j] <= x / i; j++) { //将prime[j]简称p[j]; //对于任意一个合数x，假设pj为x最小质因子，当i<=x/p[j]时，一定会被筛掉 //因为i枚举到x之前,一定会枚举到x/p[j],而当x/p[j]不就是合数x的因子， //所以x一定会被在i<=x/p[j]时被筛除。 st[prime[j]*i] = true; if(i % prime[j] == 0) break; } } }
若 i % p[j] = = 0, p[j]定为i最小质因子，p[j] 也定为p[j] * i最小质因子,
此时需要退出循环，否则接下来筛的数肯定不是它的最小质因数所筛去的。
如
21 = 3 * 7 当枚举到质因数为3时，此时 21 % 3 = = 0 应该退出若不退出的话，下一个值素数为p[j]=5。
即
21 * 5 = 105 会被5筛去，但是 105 =3 * 5 * 7 ，最小质因子应该是3，应该被3筛去，不符合算法思想。
若 i % p[j] ! = 0, pj定小于i的所有质因子，所以 p[j] 也为 p[j] * i 最小质因子。
如果读者部分细节实在理解不了，可以先尝试背过模板，先将模板熟练掌握。
完结散花
ok以上就是质数全家桶的全部讲解了，如果有遗漏、错误或者更加通俗易懂的讲解,欢迎小伙伴私信我，我在后期再补充完善。由于作者实在是太菜了，完成这篇博客真的耗费了这家伙大量精力，所以希望读者不要吝啬自己的三连好评啦嘿嘿。
