代码
不废话，上代码：
def IsPrime(n):
# 2, 3 单独处理
if n == 2 or n == 3:
return True
# 不在 6 的倍数两侧的不是素数
if n % 6 != 1 and n % 6 != 5:
return False
# 在 6 的倍数两侧的不一定是素数
for i in range(5, int(n ** 0.5) + 1, 6):
# i 的步长可以放大到 6
if n % i == 0 or n % (i + 2) == 0:
return False
return True
对比
传统的判断素数函数如下：
def IsPrime1(n):
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
运行两个函数判断素数，得到其运行时间分别如下：文章来源：https://www.toymoban.com/news/detail-408348.html
| number | IsPrime | IsPrime1 |
|---|---|---|
| 3 | 9.5367431640625e-07 | 8.58306884765625e-06 |
| 4 | 1.1920928955078125e-06 | 3.0994415283203125e-06 |
| 5 | 2.384185791015625e-06 | 1.430511474609375e-06 |
| 7 | 1.6689300537109375e-06 | 1.1920928955078125e-06 |
| 100 | 7.152557373046875e-07 | 1.6689300537109375e-06 |
| 10000 | 7.152557373046875e-07 | 1.6689300537109375e-06 |
| 100000000 | 4.76837158203125e-07 | 2.384185791015625e-06 |
可以看到总体上第一个判定素数函数是要快很多的，尤其对于大素数的判定。文章来源地址https://www.toymoban.com/news/detail-408348.html
到了这里，关于Python快速判断素数方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
