高效素数判断算法

算法概述

此算法将其他博主对基本素数算法的一些改进进行了整合，其中主要整合了如下三条规则：

1.大于3的素数一定在6的倍数前一个或后一个（如素数37在36的后面）

2.要判断n是否为素数，只需要让n从2开始，依次除到根号n即可

3.在进行“让n从2开始，依次除到根号n”过程中，若n除以2的余数不为0，可以直接跳过[2, sqrt(n)]里面的所有偶数

博主语文素养不高，表达不是很准确，在后面会对这三条规则进行解释。

规则详解

1.大于3的素数一定在6的倍数前一个或后一个（如素数37在36的后面）

• 数学证明：

任意一个整数n可以表示为n = 6a + b ( 0 <= b <= 5, a >= 0 )，接下来依次讲当n等于0到5的情况，以对此结论进行证明：

当n = 6a + 0 = 6a时，n有一个不为1及其本身的因数（素数判断条件）6，此类数不为素数

当n = 6a + 2 = 2( 3a + 1 )时，n有一个不为1及其本身的因数（素数判断条件）2，此类数不为素数

当n = 6a + 3 = 3( 2a + 1 )时，同上，有一因数3，此类数也不为素数

当n = 6a + 4 = 2( 3a + 2 )时，有一因数2， 此类数也不为素数

而当n = 6a + 1 或 n = 6a + 5时，不能绝对确定n是否为素数，需要考虑a的取值，显然此时的数值n就是分布在6的倍数前一个或后一个

总结：大于3的素数一定分布在6的倍数前后

• 此规则可以直接对素数进行初步筛选，不符合此规则的数可直接判定为非素数，直接减少了2/3的运算量，效率提高肉眼可见
• 注意小于等于3的素数(2, 3)需要另外判断

2.要判断n是否为素数，只需要让n从2开始，依次除到根号n即可

最基本的素数判断方法是：让n从2开始除，依次除到n - 1，如果每次除出来的结果余数皆不为0，那么此数n即为素数
实际上并不需要从除以[2, n - 1]区间的所有整数，只需除以[2, sqrt(n)]

3.在进行让n除以[2, sqrt(n)]区间内的所有整数操作时，如果2不是n的一个因数，那么之后可以不判断[2, sqrt(n)]区间的所有偶数

数学证明：当n/2除不尽时，n除以[2, sqrt(n)]区间内的所有偶数都除不尽

因此如果n不能将2除尽，那么之后的偶数一样除不尽，可以直接不除
如果将2除尽了，n就不是素数，直接排除
如果没有将2除尽，之后的计算量直接减半，肉眼可见的效率提升

算法时间复杂度复杂度

1.最基础的算法：也就是让n从2开始判断，一直到n-1

若遇到的数是素数时，此时需要进行n-2次判断
当遇到的不是素数时，要进行a（2<a<n-2)次判断
也就是说时间复杂度为n

2.改进后的算法：

根据规则二，判断素数只要从[2，sqrt(n)]即可，此时复杂度为sqrt(n)
根据规则3，无论如何都可以不判断2之后的偶数（当n大于2，当n除尽2时，n不为素数，之后不需要判断，如果n除不尽2时，之后的偶数不要判断）
假设n可以除尽2和不可以除尽2概率相等，那此时复杂度为sqrt(n)/4
根据规则一，只有1/3的数要进行判断，此时复杂度为sqrt(n)/12
也就是说时间复杂度为sqrt(n)/12

在计算过程中做出的假设以及计算过程并不那么严谨，此结果仅供参考

Python代码实现

def primeJudge(n):
 #先将数分为三类， 小于等于1，大于1小于5，和大于等于5
 #非整数统统不是素数
 if not isinstance(n, int): return False
 #小于1等于的都不是素数
 if n <= 1: return False
 #大于1小于5
 elif n == 2 or n == 3: return True
 #大于等于5
 elif n >= 5:
  #先判断是否在6的附近
  if n % 6 == 5 or n % 6 == 1:
   #再判断是否可以将2除尽
   #可以的话不是素数
   if n % 2 == 0: return False
   else:
    #不可除尽2，直接跳过所有偶数
    for i in range(3, int(sqrt(n) + 1), 2):
     if n % i == 0: return False
    #经过筛选即为素数
    return True
  #不在6的附近不是素数
  else: return False