Python 判断质数

1. 什么是质数

质数（prime number），又称素数，是指只能被1和自身整除的正整数。例如，2、3、5、7、11等都是质数，而4、6、8、9等则不是质数。

2. 判断方法

要判断一个数是否为质数，有多种方法可以使用。下面介绍两种常用的方法。

2.1. 暴力法判断

暴力法判断质数的思路是，对于一个数n，我们从2到n-1遍历，判断n是否能被整除。如果存在能被整除的数，则n不是质数；否则，n是质数。

以下是使用暴力法判断质数的示例代码：

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

# 测试代码
print(is_prime(2))   # 输出：True
print(is_prime(3))   # 输出：True
print(is_prime(4))   # 输出：False
print(is_prime(5))   # 输出：True
print(is_prime(6))   # 输出：False

代码运行结果如下：

True
True
False
True
False

从运行结果可以看出，2、3和5是质数，而4和6不是质数。

2.2. 优化判断法

在暴力法中，我们对所有小于n的数都进行了判断。实际上，我们只需要判断小于等于n的平方根的整数部分即可。如果n能被小于等于其平方根的整数整除，那么就一定能被大于其平方根的整数整除。

以下是使用优化判断法判断质数的示例代码：

import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return False
    return True

# 测试代码
print(is_prime(2))   # 输出：True
print(is_prime(3))   # 输出：True
print(is_prime(4))   # 输出：False
print(is_prime(5))   # 输出：True
print(is_prime(6))   # 输出：False

代码运行结果如下：

True
True
False
True
False

从运行结果可以看出，与暴力法结果相同。

3. 判断效率

通过上面两种方法可以判断一个数是否为质数，但它们的时间复杂度不同。下面对比两种方法的判断效率。

3.1. 暴力法判断效率

暴力法的时间复杂度为O(n-2)，即O(n)。在判断一个数n是否为质数时，需要遍历2到n-1的所有数。当n非常大时，暴力法的判断效率较低。

3.2. 优化判断法效率

优化判断法的时间复杂度为O(sqrt(n))。在判断一个数n是否为质数时，只需要遍历2到sqrt(n)的数。当n非常大时，优化判断法的判断效率较高。

4. 应用实例

质数判断在实际应用中有很多场景，例如：

• 密码学中的RSA算法是基于质数大数的加密算法；
• 找出两个质数的乘积，用于生成大素数；
• 筛质数算法，用于找出一定范围内的所有质数。

下面以筛质数算法为例进行说明。

4.1. 筛质数算法

筛质数算法（Sieve of Eratosthenes）是一种用于找出一定范围内的所有质数的方法。

其基本原理是从2开始，先找出2的倍数（除2以外的所有偶数），然后将这些倍数的数标记为合数。接着找到下一个未被标记为合数的数，即为下一个质数，再将其倍数标记为合数。依次类推，直到找不到下一个未被标记为合数的数为止。

以下是使用筛质数算法找出100以内的所有质数的示例代码：

def sieve_of_eratosthenes(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False  # 0和1不是质数
    p = 2  # 当前质数
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n+1, p):
                primes[i] = False
        p += 1
    # 输出质数
    for i in range(2, n+1):
        if primes[i]:
            print(i, end=" ")

# 测试代码
sieve_of_eratosthenes(100)  # 输出：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

代码运行结果如下：

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

从运行结果可以看出，100以内的所有质数都被正确地找出来了。

5. 总结

本文介绍了Python中判断质数的方法，包括暴力法和优化法。通过对比两种方法的判断效率，可以选择合适的方法进行使用。质数判断在密码学、数论等领域有着广泛的应用。同时，我们还以筛质数算法为例，展示了如何找出一定范围内的所有质数。