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）都是寻找范围内所有质数的经典算法。两者的共同目标是高效地生成质数，但它们在实现细节上有所不同，导致在效率上有一些差异。
我们以后将继续讨论其优点和实现的方法。