素数判断法

质数判断法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import math

def is_prime(x):
    if x <= 1:
        return False
    
    for i in range(2,int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
        
    return True
is_prime(17)  # True
is_prime(23)  # True
is_prime(56)  # False

说明 : 在此方法中我们从 2 开始遍历到 x 的平方根 (使用math.sqrt()获取 x 的平方根的整数部分 + 1),判断是否存在能整除 x 的数, 如果存在 x 不是素数;反之,则为素数.

时间复杂度为：

O(sqrt(x))O(sqrt(x))

相关执行过程如下：

埃氏筛 (埃拉托斯特尼筛法)

相关链接: 埃拉托斯特尼筛法 (wikipedia.org)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    primes = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)

    return primes

print(sieve_of_eratosthenes(20))

# [2, 3, 5, 7, 11, 13, 17, 19]

说明 : 起初 , 创建一个布尔数组 is_prime , 全部初始化为 True ,将索引 0 和 1 赋值为 False , 从 2 开始遍历到 n 的平方根(平方根取整+1) , 如果当前数字 i 是素数（即 is_prime[i] 为 True），则将其倍数 i*i、i*(i+1)、i*(i+2)… 标记为非素数（将对应的 is_prime[j] 置为 False）。最后，我们遍历从 2 到 n 的所有数字，将 is_prime 中值为 True 的索引添加到素数列表 primes 中。

相关执行过程如下：

O(nloglogn)O(n log log n)

总结

以上是关于质数判断法和埃拉托斯特尼筛法的 Python 示例代码和相关说明.

质数判断法 更适用于判断单个素数

埃拉托斯特尼筛法 比较适合取得一定范围内的素数序列

根据具体需求选择相应算法