1 简介
质数，也称素数，是指在大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。质数有以下性质：
质数的约数只有两个：1和它本身。
算术基本定理表明，任何一个大于1的自然数都可以唯一分解成有限个质数的乘积。
质数的个数是无限的，这是由欧几里得证明的。
除了2以外，所有的质数都是奇数。
所有大于2的质数都可以表示为6n±1的形式。
任何不是1的自然数至少存在一个质数约数。
寻找质数的方法有很多，以下是一些知名的算法：
在实际应用中，选择哪种算法取决于所需的精确度和效率。
例如，在密码学中，通常会需要非常大的质数，这时就需要使用更高效的算法来生成。质数在密码学领域扮演着重要的角色，特别是在公钥密码学中，如RSA加密算法，它使用了大质数的乘积作为公钥和私钥的一部分。
计算质数的乘积很简单，但是将大合数分解为质因数非常困难，这保证了RSA加密算法的安全性.
2 寻找质数
试除法：对每一个自然数n，从2开始试除到sqrt(n)，如果都无法整除，则n是质数。
埃拉托斯特尼筛法（Sieve of Eratosthenes）：这是一种高效的生成一定范围内所有质数的算法。它通过逐步筛除合数来找出质数。例如，找出100以内的所有质数，先把2的倍数筛掉（保留2），再把3的倍数筛掉（保留3），如此重复下去，直到7的倍数被筛掉，剩下的就是100以内的质数。
这种生成素数的想法是由希腊数学家埃拉托色尼提出的。该算法通过将数组中的所有数字标记为素数，然后划掉所有倍数（非素数）。
使用该方法的质数产生器一般也称之为埃式筛。它将目标范围的平方根内的全部非质数排除后，剩下的作为质数输出。
什么是素数 素数.“p”是一个只有两个因数的自然数，1 和数本身，即 p。即素数不能分解为超过 2 个自然数。
示例：2、3、5、7、9,…
素数的性质
除 2 外，所有质数都是奇数。
除 2 和 3 外的所有素数均为 6n+1 或 6n-1。
示例：31 = 6 * 5 + 1
示例：941 = 6 * 157 - 1
[梅森的素数]如果表格中的数字2^N-1是素数.那么 ‘n’ 必须是素数，但不能相反(如果n为素数，2^N-1不一定是)。
示例：数字 31 是素数。它的形式是 2^5-1，那么 5 必须是素数，它。
示例：数字 11 是素数。但这并不能使 2^11-1 （2047） 素数。2047 可以被 23 和 89 整除
Prime Sieve Algorithm的时间复杂度为O（N log log N）
我们将数组中的数字标记为非素数（复合）的次数是 n/2 + n/3 + n/5 + n/7 + …最多 N。
N/2 + N/3 + N/5 + N/7 + N/11…最多 n = n 。(1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ….最多 n）。
数学证明 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + …最多 n = ln ln n。
因此，n.（1/2 + 1/3 + 1/5 + 1/7 + 1/11 + …最多 n） 为：n ln ln n i.e n log l
其他方法：
试除法：对每一个自然数n，从2开始试除到sqrt(n)，如果都无法整除，则n是质数。
埃拉托斯特尼筛法（Sieve of Eratosthenes）：这是一种高效的生成一定范围内所有质数的算法。它通过逐步筛除合数来找出质数。例如，找出100以内的所有质数，先把2的倍数筛掉（保留2），再把3的倍数筛掉（保留3），如此重复下去，直到7的倍数被筛掉，剩下的就是100以内的质数。
欧拉筛法：这是一种优化的埃拉托斯特尼筛法，它利用了前缀和的概念，可以在更短的时间内找出一定范围内的所有质数。
费马小定理：这是一个关于质数的数论定理，可以用来检测一个数是否为质数。
梅森质数：梅森质数是形式为2^p-1的质数，其中p本身也是一个质数。
哥德巴赫猜想：每个不小于6的偶数都可以表示为两个质数之和，尽管这是一个猜想，但它也启发了一些寻找质数的方法。
黎曼猜想：虽然它是一个未解决的数学问题，但它与质数分布有着密切的关系。
质数定理：描述了质数在自然数中的分布情况。
2 带发生器的埃式质数筛
具有动态类型功能的 Mypy
import itertools
def iter_primes():
# An iterator of all numbers between 2 and
# +infinity
numbers = itertools.count(2)
# Generate primes forever
while True:
# Get the first number from the iterator
# (always a prime)
prime = next(numbers)
yield prime
# This code iteratively builds up a chain
# of filters...
numbers = filter(prime.__rmod__, numbers)
for p in iter_primes():
if p > 1000:
break
print(p)
具有静态类型的 Mypy
import itertools
from typing import Iterator
def iter_primes() -> Iterator[int]:
# An iterator of all numbers between 2 and
# +infinity
numbers = itertools.count(2)
# Generate primes forever
while True:
# Get the first number from the iterator
# (always a prime)
prime = next(numbers)
yield prime
# This code iteratively builds up a chain
# of filters...
numbers = filter(prime.__rmod__, numbers)
for p in iter_primes():
if p > 1000:
break
print(p)
埃式质数筛的另一个实现版本
计算函数接受定义一个名为GeneratePrimes的函数，参数是num_range，表示要生成素数的范围。
import math
def GeneratePrimes (num_range) :
# Mark all numbers as prime
#创建一个布尔值列表list_numbers，长度为num_range，初始值全部为True，表示所有数字都是素数。
list_numbers = num_range * [True]
# Cross out 0, 1 as they are not primes
# 剔除0和1，将索引为0和1的元素设为False，因为0和1不是素数。
list_numbers[0] = list_numbers[1] = False
计算num_range的平方根，并将结果转换为整数，赋值给square_root。这个值是用来减少内循环的计算量。
square_root = int(math.sqrt(num_range))
#循环从0到square_root（不包括square_root）。
for p in range(square_root) :
# 检查list_numbers中的第p个元素是否为True，即判断当前数字p是否为素数。
if (list_numbers[p] == True) :
#如果p是素数，从p的平方开始，标记所有p的倍数为非素数。
#range(p*p, num_range, p)表示从p*p开始，以p为步长，到num_range结束。
for i in range (p*p, num_range, p) :
# 将list_numbers中索引为i的元素设为False，标记为非素数。
# 因为 任何一个数的平方加上这个数本身不可能是素数 p**2 + p,
# 等同于 p(p+1), (这违背了素数的定义，只能被1和自身整除)。
# Cross out non primes by marking them false
list_numbers[i] = False
# 打印一条消息，表示将显示到num_range的素数。
print ("Primes upto "+str(num_range)+" :")
# 初始化一个变量total，用于计数素数的总数。
total = 0
# 循环遍历list_numbers列表的每个索引。
for p in range(len(list_numbers)) :
# 检查list_numbers中的第p个元素是否为True，即判断当前数字p是否为素数。
if(list_numbers[p] == True) :
# 如果p是素数，打印p，并在末尾加一个空格（而不是换行）。
print (p, end = ' ')
# 将total加1，表示找到一个素数。
total += 1
# 打印一个换行符，然后打印素数的总数total。
print("\n total:\n", total)
if __name__ == "__main__":
GeneratePrimes(100)
GeneratePrimes(1000)
GeneratePrimes(10000)
3 小结
欧拉筛法（Euler’s Sieve）和埃拉托斯特尼筛法（Sieve of Eratosthenes）都是寻找范围内所有质数的经典算法。两者的共同目标是高效地生成质数，但它们在实现细节上有所不同，导致在效率上有一些差异。
我们以后将继续讨论其优点和实现的方法。