素数专辑（超详细超完善版本）

素数的使用

1. 素数以及素数性质
2. 素数筛法
3. 素数判断法
4. 素数常见使用点
5. 总结

1.素数以及素数性质 1.1素数概念

素数，也称质数。是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

1.2素数性质

质数具有许多独特的性质： （1）质数p的约数只有两个：1和p。 （2）初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。 （3）质数的个数是无限的。 （4）质数的个数公式 是不减函数。 （5）若n为正整数，在 到 之间至少有一个质数。 （6）若n为大于或等于2的正整数，在n到 之间至少有一个质数。 （7）若质数p为不超过n（ ）的最大质数，则 。 （8）所有大于10的质数中，个位数只有1,3,7,9。

2.素数筛法（数论方法）

一般题目涉及到的素数很大时，用一般的判素方法一位一位去判断有点耗时耗力，这时候常用数论里面的筛法去筛选大素数。这里我们讲到下面两种筛法：埃斯筛法和欧拉筛法

2.1埃斯筛法（时间复杂度O(n*logn)）

埃斯筛法，全名埃拉托斯特尼筛法。 u[ ]是一个筛子，也可以看作是一个标记数组，用于标记这个数是素数还是合数 设u[ ]为筛子，初始时区间中的所有数在筛子u[]中。按递增顺序搜索u[]中的最小数， 将其倍数从u[]中筛去，最终筛中留下的数即为素数。 算法代码如下：

默认使用c++语言
 int i, j, k;
 for (i=2; i