avatar

关于递归构造素数的方法

关于递归构造素数的方法

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

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

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

比如
$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实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 列表元素的乘积
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)

结语

如果以后哪次还看到什么关于这方面的小知识,可能会来更新…

文章作者: XeanYu
文章链接: http://www.xeanyu.club/2020/05/10/%E5%85%B3%E4%BA%8E%E9%80%92%E5%BD%92%E6%9E%84%E9%80%A0%E7%B4%A0%E6%95%B0%E7%9A%84%E6%96%B9%E6%B3%95/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 XeanYu's Blog
打赏
  • 微信
    微信
  • 支付寶
    支付寶