素数的定义
如果一个数不能整除比它小的任何素数，那么这个数就是素数
素数的应用
素数有很好的数学特性， 很多数学理论都用到了素数， 计算机里常用的产生随机数，hash算法，RSA非对称加密算法等都用到了素数
如何判断一个数是否是素数
朴素算法
根据素数定义判定
给定一个数n，i 从 2 开始取值，直到 n - 1(取整数),如果 n % i != 0 , n 就是素数
实际上 除了1以外，任何合数最小的因子就是2，那最大的因子就是 n/2， 那我们就遍历到 n/2就足够了
再进一步其实我们遍历到 sqrt(n); 就行了
go实现
func IsPrimeLow(n int) bool {
if n < 2 {
return false
}
max := int(math.Sqrt(float64(n)))
//max := n/2
for i := 2; i <= max; i++ {
if n%i == 0 {
return false
}
}
return true
}
素数判别法
根据上面的例子如果我们输入的数是67， 那么Max 是sqrt(67) 取整得8; 我们要挨个去用{2,3,4,5,6,7,8}去试， 其中{4，6，8}都是2的倍数；假如67不能被2整除， 那么一定不能被{4，6，8}整除，后面的对{4,6,8}的判定都是多余的， 所以算法可以改进为：
给定一个数n，循环小于sqrt(n)的所有素数,取当前值为i, 如果 n % i != 0 , n 就是素数
该算法的关键在于求取指定数字以内的所有素数；（感觉是个圈）
大致思路：
1、我们可以先设定小于10的素数集合{2,3,5,7} 那么我们就可以遍历10～100的数 通过该判定方法求出100以内的质数集合
2、拿着100以内的质数集合，取求取小于10000的质数集合
3、依次类推，求出100 000 000 以内的质数集合
4、10000以内的质数是有限的，为1229个，可以先求出来，写死在一个数组里，以此为基础，以空间换时间， 就能轻松判定1亿以内的任意数字是否为素数
5、UInt64 代表无符号的最大值为： 18446744073709551615 开平方得到：4294967296 那么我们也可以求出4294967296内的所有质数，以此为基础，解决目前计算机常态下的素数运算问题
埃拉托斯特尼(Eratosthenes)筛法
该方法是古希腊数学家埃拉托斯特尼提出，用于获取指定数字n以内的所有素数集合， 他其实是利用了空间换时间的方式; 先从2开始累加生成一个数组a包含小于n的所有整数；然后从a[i+1]遍历除以a的第一个元素a[0]=2；如果能被2整除，则标记为false，循环结束后再进入下一轮循环，除以第一个没有被标记的数字，如果之前标记过，就跳过否则，判断是否被整除，如果能够整除则标记为fales， 知道被除数大于sqrt(n)，打印出所有未被标记的数字
php的实现(为什么要说php好呢？只用专注逻辑实现，写出来的东西更像其他语言的伪代码，结构清晰)
function Primenumber($n){
if($n<=1){
return array();
}
// 构造数组
$arr = [];
for($i=2;$i<=$n;$i++){
$arr[$i]=true;
}
// 逐个标记
$p=2;
$maxp = intval(sqrt($n));
while($p<=$maxp){
$nextp = 0;
// 遍历
for($i=$p+1;$i<=$n;$i++){
if($arr[$i]==true && $i%$p==0){
$arr[$i]=false; //标记
}else{
// 产生下一个循环被除数
if($arr[$i]==true){
$nextp = $nextp==0?$i:$nextp;
}
}
}
$p =$nextp;
}
// 获取为true的标记位
$primes=[];
for($i=2;$i<=$n;$i++){
if($arr[$i]==true){
$primes[] = $i;
}
}
return $primes;
}
这个方法的缺点就是空间浪费太大，其实仔细分析下
此筛法的原理是：想要取得不大于n的自然数内所有的素数，就要把小于√n的所有素数的倍数剔除掉。
go的实现
以下算法可以节省一定的空间，但是要计算若干次sqrt(n), 这里我用了自带函数，实际求解sqrt(n)， 也不是很容易，一定程度上还是比埃拉托斯特尼筛法要低；
func Primenumber(num uint64, primes []uint64) []uint64 {
if num < 2 {
return nil
}
maxp := uint64(math.Sqrt(float64(num)))
max_prime := primes[len(primes)-1]
if max_prime < maxp {
primes = Primenumber(maxp, primes)
}
primeList := primes
for i := primes[len(primes)-1] + 1; i <= num; i++ {
isPrime := true
for _, n := range primes {
if i%n == 0 {
isPrime = false
break
}
}
if isPrime == true {
primeList = append(primeList, i)
}
}
return primeList
}
质数分布的规律
大于等于5的质数一定和6的倍数相邻
例如5和7，11和13,17和19等等；
证明：令x≥1，将大于等于5的自然数表示如下：
··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ···
可以看到，不和6的倍数相邻的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧
但是6x两侧的数也不一定是质数，还得判断是否是6y+1， 6y+5的倍数（ y < x ） 例如25，是64+1， 在64的右边，但是是6*0+5的倍数就不是质数
大素数判别
上述方法里我们可以很容易判别UInt64以内的素数，但是如果要对一个工业级的大素数进行判别就不那么容易了
比如：RSA 算法里需要找到一个512位的大素数，该怎么办？
思路很简单，就是找到一个512位的数字区间， 遍历每一个数，检查其是否为素数，如果是就返回
但是如何判别一个512位的数字是否是素数呢？ 用之前的方法效率极其低下
一般做法是经过若干次米勒-罗宾（Miller-Robin）素性测试，检查通过就认为其为素数
这里不做展开，计划单独开一篇文章做详细阐述 https://www.cnblogs.com/Norlan/p/5350243.html