求质数(素数)的几种方法

本文简单介绍几种判断一个数是否为质数的算法,并给出 Python 语言的实现。

质数的定义

  1. 质数又称素数,是一个大于1的自然数。该数只能被1和它自身整除

  2. 如果一个数不是质数,则称为合数。

  3. 0和1既不是质数也不是合数,最小的质数是2

完全枚举法

假设有大于一的自然数 n,要判定 n 是否为质数,则可以用大于1,小于n 的数顺位为 n 取余,只要其中有一个余数为零,则 n 为合数,如果都不为零,则 n 为质数。

代码实现如下:

1
2
3
4
5
6
7
8
9
def isPrime(num):
if num <= 3:
return num > 1
ok = True
for i in range(2, num):
if num % i == 0:
ok = False
break
return ok

改进方法

用上一种方法虽然可以正确得到结果,但如果 n 非常大,则枚举的数量也非常大(3 ~ n - 1), 非常低效,因此需要更高效的方法。根据数学理论,一个合数可以分解为两个非1的约数p1和p2,其中p1<=sqrt(n),p2>=sqrt(n), 因此我们只需要判断在 3 ~ p1 的区间中是否有一个数可以整除n, 如果有,则n为合数,否则为质数。这样就把区间大大缩小了,比如要判断101 是否为质数,按照上一种方法,需要判断 99 次, 而采用这种这种方法,只需要判断 9 次即可,大幅提高了效率。

实现代码如下:

1
2
3
4
5
6
7
8
9
10
def isPrime(num):
if num <= 3:
return num > 1
num2 = round(num ** 0.5) # 平方根
ok = True
for i in range(2, num2 + 1):
if num % i == 0:
ok = False
break
return ok

继续改进

根据数学分析,质数还有一个提点: 就是它总是等于 6x-1 或者 6x+1,其中 x 是大于等于1的自然数。

为直观的说明,我们先打印一下 100 以内的 6x - 1 和 6x + 1 的数来看看:

1
5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97

我们在打印一下 100 以内的质数(为方便比较,只列出大于3的部分)

1
5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

可以看到,其中只有:

1
25, 35, 49, 55, 65, 77, 85, 91, 95

而这些数都是能被 6x -1 或 6x + 1 整除的。

根据以上特点,我们可以在前一个程序基础上继续优化,得到如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
def isPrime(num):
if num <= 3:
return num > 1
if num % 6 != 1 and num % 6 != 5:
return False
ok = True
num2 = round(num ** 0.5)
for i in range(5, num2 + 1, 6):
if num % i == 0 or num % (i + 2) == 0:
ok = False
break
return ok

那么这个算法判断 101 是否是质数需要判断几次呢? 答案是 1 次, 是不是效率大幅提高了。

本文标题:求质数(素数)的几种方法

文章作者:晨星

发布时间:2020年04月01日 - 21:04

最后更新:2020年09月16日 - 08:09

原始链接:https://www.mls-tech.info/python/python-algorithm-prime/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。