极客教程Python 求质数
介绍
在数学中，质数（prime number）又称素数，是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。质数在数论以及密码学等领域有着重要的应用，因此求质数是一个常见的问题。
在本文中，我们将使用 Python 编程语言来实现求质数的算法。我们将介绍两种常见的算法：试除法和埃拉托斯特尼筛法。
试除法
试除法是一种直接且容易实现的求质数的算法。它基于质数的定义，从2开始遍历到待测试的数的平方根，逐个试除，如果存在能整除待测试数的因子，则该数不是质数，否则是质数。
下面是使用试除法实现的一个求质数的函数：
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
函数 is_prime(num) 接受一个整数参数 num，判断该数是否为质数。首先判断参数是否小于2，如果是，则直接返回 False。然后，使用一个循环从2到 num 的平方根（加1）进行遍历。在循环体内，使用取余运算判断 num 是否能被当前循环变量 i 整除，如果能整除，则返回 False，表示 num 不是质数。如果循环结束后都没有找到能整除 num 的因子，返回 True，表示 num 是质数。
接下来，我们可以使用该函数来判断一个范围内的所有质数。下面是一个示例代码，用于打印1到100之间的所有质数：
for num in range(1, 101):
if is_prime(num):
print(num)
运行上述代码，将会输出1到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
从输出结果可以看出，1到100之间一共有25个质数。
试除法是求质数的简单算法，但是在处理大范围的数时效率较低。接下来，我们将介绍一种更高效的算法。
埃拉托斯特尼筛法
埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效的求质数的算法。它的基本思想是从2开始，将每个质数的倍数全部标记为合数，直到遍历完所有小于等于待测试数的数。
下面是使用埃拉托斯特尼筛法实现的一个求质数的函数：
def get_primes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
return [num for num in range(n + 1) if primes[num]]
函数 get_primes(n) 接受一个正整数参数 n，返回小于等于 n 的所有质数。首先，创建一个长度为 n + 1 的布尔列表 primes，并将所有元素初始化为 True。然后，将列表的第一个和第二个元素设置为 False，因为它们不是质数。接下来，使用一个循环从2到 n 的平方根进行遍历，如果当前数 p 是质数，则将其所有倍数都标记为合数，即将对应索引的布尔值设置为 False。最后，使用列表推导式生成所有值为 True 的对应索引，即为小于等于 n 的所有质数。
接下来，我们可以使用该函数来打印小于等于100的所有质数。示例代码如下：
primes = get_primes(100)
for prime in primes:
print(prime)
运行上述代码，将会输出小于等于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
从输出结果可以看出，小于等于100的质数与使用试除法得到的结果相同。
埃拉托斯特尼筛法通过标记倍数的方式避免了重复的试除操作，因此在处理大范围的数时效率更高。
总结
通过试除法和埃拉托斯特尼筛法，我们可以用 Python 简单而高效地求解质数。试除法是一种直接的判断方法，适用于小范围的数，而埃拉托斯特尼筛法通过标记倍数的方式避免了重复的试除操作，适用于大范围的数。
在实际应用中，我们可以根据具体的需求选择合适的算法来求解质数，以提高程序的效率。