Python快速判断素数方法

代码

不废话，上代码：

defIsPrime(n):# 2, 3 单独处理if n ==2or n ==3:returnTrue# 不在 6 的倍数两侧的不是素数if n %6!=1and n %6!=5:returnFalse# 在 6 的倍数两侧的不一定是素数for i inrange(5,int(n **0.5)+1,6):# i 的步长可以放大到 6if n % i ==0or n %(i +2)==0:returnFalsereturnTrue

对比

传统的判断素数函数如下：

defIsPrime1(n):if n <=1:returnFalsefor i inrange(2,int(n **0.5)+1):if n % i ==0:returnFalsereturnTrue

运行两个函数判断素数，得到其运行时间分别如下：
numberIsPrimeIsPrime139.5367431640625e-078.58306884765625e-0641.1920928955078125e-063.0994415283203125e-0652.384185791015625e-061.430511474609375e-0671.6689300537109375e-061.1920928955078125e-061007.152557373046875e-071.6689300537109375e-06100007.152557373046875e-071.6689300537109375e-061000000004.76837158203125e-072.384185791015625e-06
可以看到总体上第一个判定素数函数是要快很多的，尤其对于大素数的判定。