关于递归构造素数的方法

素数及其素数在数学中的地位

在纯数学有这样一句话：“数学是科学的皇后，而数论是数学的皇后 ”

而在数论里，最基本、最重要的一类数就是素数。
而原因就在于大多数整数都可以分解较小的因子。

比如
$10 = 2 * 5$
$111 = 3 * 37$
等等…

而有这样一类数，他们是无法进行分解的，这类数就是素数。更准确的说，一个大于1的正整数p，除了 $1$ $and$ $p$ 之外就没有其他因子。

简单定义：

素数：存在一个正整数p，且p > 1，除1 及其本身p以外没有其他因子的数称为素数（质数）。

因为它是无法再分的，并且每一个整数，若不是素数的数，都可以写成素数的乘积。而这类可再分的数称为合数

因为素数是基础，所以研究它是十分重要的。

素数有无穷个证明

在发现素数的重要性后，我们要考虑，素数是否像自然数，整数一样有无穷个。
答案是：有无穷多个素数

关于素数有无穷多个的证明，十分经典的就是欧几里得利用反证法证明了素数有无穷多个。

其具体证明过程如下：

假设素数有穷个，其数量为 $n$ 个。
现有素数 $p_1、p_2、p_3、p_4 ….. p_n$ 来表示所有素数，那么所有组成相乘得到合数的素数都在此。

现在有数 $A$,
$$ A = p_1p_2p_3p_4p_5….p_n + 1$$

现在 $A$ 由所有的素数相乘并且加1得到，那么所有素数 $p$ 去除 $A$ 都会余1
如：

$$ A \div p_1 = p_2p_3p_4p_5…..p_n \quad······ 1 $$
$$ A \div p_2p_1 = p_3p_4p_5…..p_n \quad ······ 1 $$

此时会发现，$A$ 也是一个无法再分解的数，就是说 $A$ 也是一个素数.
那么现在素数就有 $n+1$ 个,不符合我们的假设素数有穷,并且有n个.

假如我们再构造一个数 $B$,且 $B$ 满足式子
$$B = Ap_1p_2p_3p_4p_5….p_n + 1$$
我们会发现利用这种方法,我们可以一直构造下去,则将会有无穷多个素数.
则素数为有穷个的假设不成立.

递归构造素数

在上面证明素数无穷个的方法中,我们可以看到一种构造素数的方法.

即:
假设有数 $A$ ,现在有素数 $p_1$ $p_2$,那么我们可以得到素数
$$
A = p_1p_2 + 1
$$
$A$ 为新的素数.

由此,我们现在知道最小的素数2,我们就可以构造出无穷多个素数.
假设有数 $P_3$,有素数$P_1 = 2$ $P_2 = 3$
那么有:
$$ P_3 = P_1*P_2 + 1 \Rightarrow P_3 = 7 $$

再假设有数 $P_4$ 有素数$P_1=2$ $P_2=3$ $P_3=7$
那么有:

$$ P_4 = P_1P_2P_3 + 1 \Rightarrow P_4 = 43 $$

$$ ……. $$

由此,从最简单的慢慢递归到越来越多…

Python实现

# 列表元素的乘积
def Product(PrimeNumberList):
    A = 1
    for i in PrimeNumberList:
        A = A * i
    return A

# 初始化素数
PrimeList = [2,3]

# 表示产生多少个素数
n = 10

# For循环获得新的素数
for i in range(0,n):

    # 构造新的素数
    NewPrimeNumber = Product(PrimeList) + 1
    
    # 新的素数加入素数列表
    PrimeList.append(NewPrimeNumber)

# 打印素数列表
print(PrimeList)