质数的性质和埃式质数筛

质数的性质和埃式质数筛

质数，也称素数，是数学中一个非常重要的概念。它们在密码学、计算机科学等领域有着广泛的应用。本文将介绍质数的基本性质，以及如何使用埃拉托斯特尼筛法（埃式筛）高效地寻找质数。

1. 质数简介

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

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

质数在密码学领域扮演着重要的角色，特别是在公钥密码学中，如RSA加密算法，它使用了大质数的乘积作为公钥和私钥的一部分。计算质数的乘积很简单，但是将大合数分解为质因数非常困难，这保证了RSA加密算法的安全性。

2. 寻找质数的方法

试除法

试除法是最基本的寻找质数的方法。对于每一个自然数n，从2开始试除到sqrt(n)，如果都无法整除，则n是质数。

埃拉托斯特尼筛法（埃式筛）

埃拉托斯特尼筛法是一种高效的生成一定范围内所有质数的算法。它通过逐步筛除合数来找出质数。例如，找出100以内的所有质数，先把2的倍数筛掉（保留2），再把3的倍数筛掉（保留3），如此重复下去，直到7的倍数被筛掉，剩下的就是100以内的质数。

这种生成素数的想法是由希腊数学家埃拉托色尼提出的。该算法通过将数组中的所有数字标记为素数，然后划掉所有倍数（非素数）。使用该方法的质数产生器一般也称之为埃式筛。它将目标范围的平方根内的全部非质数排除后，剩下的作为质数输出。

其他方法

• 欧拉筛法：这是一种优化的埃拉托斯特尼筛法，它利用了前缀和的概念，可以在更短的时间内找出一定范围内的所有质数。
• 费马小定理：这是一个关于质数的数论定理，可以用来检测一个数是否为质数。
• 梅森质数：梅森质数是形式为2^p-1的质数，其中p本身也是一个质数。
• 哥德巴赫猜想：每个不小于6的偶数都可以表示为两个质数之和，尽管这是一个猜想，但它也启发了一些寻找质数的方法。
• 黎曼猜想：虽然它是一个未解决的数学问题，但它与质数分布有着密切的关系。
• 质数定理：描述了质数在自然数中的分布情况。

3. 带发生器的埃式质数筛

动态类型实现

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)

静态类型实现

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)

4. 埃式质数筛的另一种实现版本

import math
def GeneratePrimes (num_range) :
    # Mark all numbers as prime
    list_numbers = num_range * [True] 
    # Cross out 0, 1 as they are not primes
    list_numbers[0] = list_numbers[1] = False
    square_root = int(math.sqrt(num_range))
    for p in range(square_root) :
        if (list_numbers[p] == True) :
            for i in range (p*p, num_range, p) : 
                list_numbers[i] = False
    print ("Primes upto "+str(num_range)+" :")
    total = 0
    for p in range(len(list_numbers)) :
        if(list_numbers[p] == True) :
            print (p, end = ' ')
            total += 1
    print("\n total:\n", total) 
if __name__ == "__main__":
    GeneratePrimes(100)
    GeneratePrimes(1000)
    GeneratePrimes(10000)

5. 小结

欧拉筛法（Euler’s Sieve）和埃拉托斯特尼筛法（Sieve of Eratosthenes）都是寻找范围内所有质数的经典算法。两者的共同目标是高效地生成质数，但它们在实现细节上有所不同，导致在效率上有一些差异。我们以后将继续讨论其优点和实现的方法。