极客教程Python中质数怎么求
一、什么是质数？
在数学中，质数（Prime number），又称素数，是指一个大于1的自然数，除了1和它本身之外，不能被其他自然数整除的数。
质数是数学中的一个重要概念，在密码学、因式分解等领域有广泛的应用。
二、判断一个数是否为质数
判断一个数是否为质数有很多方法，以下介绍两种常用的方法。
2.1 方法一：试除法
试除法是最简单直观的判断方法，思路是将目标数 n 除以小于 n 的自然数，如果能整除则 n 不是质数，否则 n 是质数。
以下是使用试除法判断一个数是否为质数的代码示例：
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
以上代码中，首先判断 n 是否小于等于 1，如果是，则直接返回 False。然后使用一个循环，从 2 开始逐个试除小于等于 n 的平方根的自然数，如果能整除，则返回 False，说明 n 不是质数；如果循环结束后都没有找到能整除的数，则返回 True，说明 n 是质数。
接下来，我们分别对一些数进行测试：
print(is_prime(2)) # True
print(is_prime(7)) # True
print(is_prime(10)) # False
print(is_prime(15)) # False
print(is_prime(23)) # True
运行结果如下：
True
True
False
False
True
通过以上测试可以看出，2、7和23都是质数，而10和15都不是质数。
2.2 方法二：埃氏筛法
埃氏筛法（Sieve of Eratosthenes）是利用筛选法进行质数判断的一种简单高效的方法。
以下是使用埃氏筛法判断一个数是否为质数的代码示例：
def is_prime(n):
if n <= 1:
return False
sieve = [True] * (n + 1) # 初始化一个长度为 n+1 的布尔数组，全部设置为 True
sieve[0] = sieve[1] = False # 将 0 和 1 设为非质数
for i in range(2, int(n ** 0.5) + 1):
if sieve[i]:
for j in range(i * i, n + 1, i):
sieve[j] = False
return sieve[n]
以上代码中，首先判断 n 是否小于等于 1，如果是，则直接返回 False。然后初始化一个长度为 n+1 的布尔数组 sieve，并将 0 和 1 设为非质数。
接着从 2 开始，逐个遍历小于等于 n 的平方根的自然数，如果 sieve[i] 为 True，说明 i 是质数，然后将 i 的倍数（除了 i 本身）全部设为非质数，即 sieve[j] = False。最后返回 sieve[n] 的值，即判断数 n 是否为质数。
接下来，我们分别对一些数进行测试：
print(is_prime(2)) # True
print(is_prime(7)) # True
print(is_prime(10)) # False
print(is_prime(15)) # False
print(is_prime(23)) # True
运行结果如下：
True
True
False
False
True
通过以上测试可以看出，2、7和23都是质数，而10和15都不是质数。
三、求质数的方法
3.1 方法一：列举法
列举法是最直观的求质数的方法之一，即从小到大列举自然数，对每个数判断是否为质数。
以下是使用列举法求质数的代码示例：
def find_primes(n):
primes = []
for num in range(2, n+1):
if is_prime(num):
primes.append(num)
return primes
以上代码中，首先创建一个空列表 primes 用于存储质数。
接着使用一个循环，从 2 开始逐个判断每个数是否为质数（调用 is_prime 函数）。如果是质数，则将其添加到 primes 列表中。
最后返回 primes 列表。
接下来，我们分别求解一些范围内的质数：
print(find_primes(10)) # [2, 3, 5, 7]
print(find_primes(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]
print(find_primes(1000)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... , 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
运行结果如下：
[2, 3, 5, 7]
[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, 101, 103, 107, 109, 113, 127, 131, 137,
139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, ... , 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
以上分别求解了 10、100 和 1000 以内的质数。