质数的性质和埃式质数筛

质数的性质和埃式质数筛

质数，也称素数，是指在大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。质数在密码学领域扮演着重要的角色，特别是在公钥密码学中，如RSA加密算法，它使用了大质数的乘积作为公钥和私钥的一部分。本文将介绍质数的性质和埃式质数筛算法。

1 简介

质数，也称素数，是指在大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。质数有以下性质：

• 质数的约数只有两个：1和它本身。
• 算术基本定理表明，任何一个大于1的自然数都可以唯一分解成有限个质数的乘积。
• 质数的个数是无限的，这是由欧几里得证明的。
• 除了2以外，所有的质数都是奇数。
• 所有大于2的质数都可以表示为6n±1的形式。
• 任何不是1的自然数至少存在一个质数约数。

寻找质数的方法有很多，以下是一些知名的算法：

• 试除法：对每一个自然数n，从2开始试除到sqrt(n)，如果都无法整除，则n是质数。
• 埃拉托斯特尼筛法（Sieve of Eratosthenes）：这是一种高效的生成一定范围内所有质数的算法。它通过逐步筛除合数来找出质数。例如，找出100以内的所有质数，先把2的倍数筛掉（保留2），再把3的倍数筛掉（保留3），如此重复下去，直到7的倍数被筛掉，剩下的就是100以内的质数。
• 欧拉筛法：这是一种优化的埃拉托斯特尼筛法，它利用了前缀和的概念，可以在更短的时间内找出一定范围内的所有质数。
• 费马小定理：这是一个关于质数的数论定理，可以用来检测一个数是否为质数。
• 梅森质数：梅森质数是形式为2^p-1的质数，其中p本身也是一个质数。
• 哥德巴赫猜想：每个不小于6的偶数都可以表示为两个质数之和，尽管这是一个猜想，但它也启发了一些寻找质数的方法。
• 黎曼猜想：虽然它是一个未解决的数学问题，但它与质数分布有着密切的关系。
• 质数定理：描述了质数在自然数中的分布情况。

在实际应用中，选择哪种算法取决于所需的精确度和效率。例如，在密码学中，通常会需要非常大的质数，这时就需要使用更高效的算法来生成。质数在密码学领域扮演着重要的角色，特别是在公钥密码学中，如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）都是寻找范围内所有质数的经典算法。两者的共同目标是高效地生成质数，但它们在实现细节上有所不同，导致在效率上有一些差异。

我们以后将继续讨论其优点和实现的方法。