素数也叫做质数，是指除1和本身以外，没有其他因数的数，是数论里面的一个非常经典的概念，我们耳熟能详的哥德巴赫猜想就是一道有关素数的题目。因为素数是随机的出现在数轴上的，几乎无法预测，要判定一个数是否是素数，只有从2开始，逐步排查，直到把所有的可能性都排除掉之后，才能直到是否是素数，这就代表更本没有捷径可循。这是10万以内的所有素数的分布，以极坐标的方式绘制出来的图形： 可以看见，随着数值的增大，素数的间隔也在增大，通过密度图可以很明显的看出来： 离中心越远，密度就越低，呈现了非常明显的同心圆状态。那么是否存在一种可能性，当数字大到一定程度之后，素数就突然消失了呢？当然这个猜想在古希腊欧几里得时候就被证明了，素数是无穷的，无论大到什么级数，素数都不会消失。欧几里得素数无限定理的证明：
如果大到一定程度时候，素数会消失，则代表素数是有限的，如果是有限的，则就会最后一个素数，即最大素数。
假设素数只有有限个，按照大小顺序排列，分别记为：p1,p2,p3……pn。则最大的素数是pn。设所有素数的乘积加1为：s = (p1 * p2 * p3 …… * pn) +1
那么我们来看看s是什么？
如果s是素数，则表示pn不是最大素数了，与假设矛盾。
如果s是合数，s不能被做为他因数存在的已知素数整除。
所以得出矛盾，说明原来假设素数是有限的是错误的。
欧几里得素数无限定理，也就是“存在无限个素数”这一定理，被视为数学史上最美丽的定理之一。以研究数论而闻名的英国数学家哈代，将其视为“严肃的”定理的一个很好的例子。它包含了“重要的”想法，也就是说，此定理具有普遍性和深刻性。而孪生素数，指的是两个素数之间真好相差为2的两个，例如3和5，5和7，11和13，这样的。(当然，后面有衍生出三胞胎素数、四胞胎素数，不过都是孪生素数的变种)。那么就来了第二个猜想：素数的分布变稀松，那么孪生素数是否会消失呢？这个就是著名的“孪生素数猜想”，目前这个距离攻克这个猜想最近的人，是华裔数学家张益唐，他发表的论文，把两对孪生素数之间的距离缩小到了7000万，后来的数学家在他的理论上推导出，这数字可以小于246，即出现了一对孪生素数之后，在其后的246个数值之内，一定会出现第二对孪生素数。有关素数的问题还是很有意思的，数学人类思维的极限运动之一，而数论则被称为数学皇冠上的明珠，有兴趣的同学可以自己去了解一下。1. 暴力判定法
要求N是否是素数，依次用N除以，从2开始，一直到sqrt(n)的所有数，如果有任何一个可以整除，则表示N不是素数，方法如下：2. 偶数优化法
一个素数，必然不可能是偶数做为他的因素，因为如果你有偶数做为因素，因数为2的时候就被除尽了，所以我们可以把所有的偶数去掉，不参与计算，算法如下：可以看见，正好优化了2倍的效率，算法复杂度是O(log(n)/2)
3. 排出已有因数法
从1开始数，每6个数为1组，其中每一组的2、3、4、6的数可以表示成6k+2、6k+3、6k+4、6k+6，很明显这些数都能被2和3整除，所以我们对2和3进行检测后，这些数就可以不用检测了，而可能出现的素数在6k+1和6k+5位置上，这些数并没有被检测过，所以需要我们求取检测(虽然这些检测仍存在重复)。因为1既不是素数也不是合数，所以我们可以把需要检测的数标记为6k-1和6k+1，并从5开始检测。可以看见，正好比方法1优化了3倍的效率，算法复杂度是O(log(n)/3)上面的几种算法，一般试用于单个素数的判定，如果我们想获取某一区间所有的素数，用这种逐个判断的方法，计算开销就很庞大了，所以如果需要获取某一区间的所有素数，我们就需要用其他的方法，例如筛选法，最出名的筛选法就是埃拉托斯特尼筛法。他的原理就是逐个筛选掉素数的倍数，留下没有筛掉的自然就是素数了，比如从2开始，先把2的倍数筛掉，然后把3的倍数筛掉……当我们要求100万以内有多少个素数的时候，筛选法的效率，是逐个计算的5倍以上。当然，如果你还要极限优化的话，还可以使用numba进行静态编译，当然还可以使用Rust 的PyO3进行编程，这个内容参考以前的文章：https://gitee.com/godxia/blog
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
