代码
不废话,上代码:
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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
对比
传统的函数如下:
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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
运行两个函数判断素数,得到其运行时间分别如下:
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 |
可以看到总体上第一个判定函数是要快很多的,尤其对于大素数的判定。