Python 高效优化判断是否为素数(质数)

项目需要,在写算法的时候需要用到素数的判断,就简单的研究了一下,常见的素数判断方式就是直接写一个循环 来判断能否整除。不过这样其实并不是一个高效的判断方式,因为涉及到很多无意义的判断,在数据量较大时会影响程序运行效率。这里也不过多解释了,代码中我都做了详细注释可以很轻松看懂。

常见的素数判断代码

while True:
    num = int(input('请输入一个数:'))
    for i in range(2,num):#判断在num之前的数能不能把num整除
        if(num%i == 0):
            print('%d不为素数'%num)
            break
        else:
            print('%d为素数'%num)
            break

优化后的素数判断代码

#!/usr/bin/ python
# -*- coding: UTF-8 -*-
import math




def primeJudge(n):
    #先将数分为三类, 小于等于1,大于1小于5,和大于等于5
    #非整数统统不是素数
    if not isinstance(n, int): 
        print("非素数")

    #小于1等于的都不是素数
    if n <= 1 or n==4: 
        print("非素数")
    #大于1小于5
    elif n == 2 or n == 3: 
        print("素数")
    #大于等于5
    elif n >= 5:
    #先判断是否在6的附近
        if n % 6 == 5 or n % 6 == 1:
            #再判断是否可以将2除尽
            #可以的话不是素数
            if n % 2 == 0: 
                print("非素数")
            else:
                #不可除尽2,直接跳过所有偶数
                for i in range(3, int(math.sqrt(n) + 1), 2):
                    if n % i == 0: 
                        print("非素数")
                #经过筛选即为素数
                print("素数")
        #不在6的附近不是素数
        else: 
            print("非素数")


for i in range(1000):
    n=i
    print(n)
    primeJudge(n)

下面是关于这个算法的详细解读,只考虑应用的话读到这里就可以复制粘贴拿去用了。

算法概述

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

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

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

3
0