19 - 素数的收官：哥德巴赫猜想

鱼C-小师妹

在线讲解：





经过前面 3 讲关于素数的讨论，这是我们素数的收官之战：哥德巴赫猜想

相信童鞋们或多或少都听过“哥德巴赫猜想”这个东东，这里小师妹就简单再啰嗦一小下：

哥德巴赫猜想（Goldbach's conjecture）是数论中存在最久的未解问：

用现代的数学语言，哥德巴赫猜想可以陈述为：任一大于 2 的偶数，都可表示成两个素数之和。

这个猜想与当时欧洲数论学家讨论的整数分拆问题有一定联系。

整数分拆问题是一类讨论“是否能将整数分拆为某些拥有特定性质的数的和”的问题。

比如能否将所有整数都分拆为若干个完全平方数之和，或者若干个完全立方数的和等。

而将一个给定的偶数分拆成两个素数之和，则被称之为此数的哥德巴赫分拆。

例如：

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
14 = 3 + 11 = 7 + 7

而我们这次要做的就是求解：

2333 以内的不小于 4 的正偶数都能够分解为两个素数之和。

为了验证歌德巴赫猜想对 2333 以内的正偶数都是成立的，要将整数分解为两部分，然后判断分解出的两个整数是否均为素数。

若是，则满足题意，否则应重新进行分解和判断。

针对该问题，我们可以给定如下的输入和输出限定。

输入时：

每行输入一组数据，即 2333 以内的正偶数n ，一直输入到文件结束符为止。

输出时：

输出 n 能被分解成的素数 a 和 b。如果不止一组解，则输出其中 a 最小的那组解。

当然，肯定要根据实际的需要规定不同的输入和输出形式。

例如输入：

4
6
8
10
12

输出：

2 2
3 3
3 5
3 7
5 7

通过上面的分析，我们需要两个自定义函数，来实现两个功能：

• 判断素数
• 验证猜想
  

判断素数的我们已经用过很多次啦，就不废话了，prime() 拿来直接调用：

def prime(n):
    m = math.sqrt(n)
    i = 2
    while i <= m:
        if n % i == 0:
            return 0
        i += 1
    return 1

重点在下面的验证猜想。

由于我们已经对输出做了限定，即当输出结果时，如果有多组解，则输出 a 最小的那组解。


为了防止有些鱼油故意输入奇数，我们用一个小判断来告诉他们按要求输入：

if (n%2) != 0:
        print("这是奇数噢，请输入大于4的正偶数")
        return

然后我们对每个读入的数据 n，a 必然小于或等于 n//2，因此，定义循环变量 i。

使其从 2～n//2 进行循环，每次循环都判断 prime(i) 和 prime(n-i) 是否为 1。

如果 prime(i) 和 prime(n-i) 为 1，此时 i 和 n-i 都为素数，又由于 i 是从 2～n/2 按由小到大的顺序来迭代的。

因此（i,n-i）是我们求出的一组解，且该组解必然是所有可能解中 a 值最小的。

还需要注意的是，由于除了 2 以外的偶数不可能是素数。

因此，i 值的可能取值只能是 2 和所有的奇数。

那我们就将上面的函数取名为 guess() ，功能就是验证传入的参数 n 是否满足哥德巴赫猜想。

代码其实不难，一个 while 循环搞定：

游客，如果您要查看本帖隐藏内容请回复

既然是验证，就不能像之前一样执行一次就结束，需要反复执行输出结果。

主框架还是用 while 循环，每输入一个数据就处理一次，直到人为结束程序或输入非法数据而终止输入：

if __name__ == "__main__":
    while True:
        print("请输入一个不小于4的正偶数：")
        n = int(input())
        guess(n)

if __name__ == '__main__' 的意思就是当 .py 文件被直接运行时，if __name__ == '__main__'之下的代码块将被运行。

好啦，这里执行下看结果：



源码： 19.py.zip (949 Bytes, 下载次数: 12, 售价: 8 鱼币)

2021-11-9 20:30 上传

点击文件名下载附件

核心代码都有了，完整代码留给你们当作业！

好了，下课！

Max472

1

金貔貅

6666666666666

hornwong

说与山鬼听os

666

madlzy

xueyixia

yangtao120

wbing

膜

TramBradr

mod

小薛王

学习学习

唯爱编程

·1

游刃鱿鱼

把素数搞懂了一起就好办了！

even = int(input('请输入一个不小于4的正偶数：'))
for i in range(2,even):
    for n in range(2,i):
        if  i % n == 0:
            break
    else:
        j = even - i
        for n in range(2,j):
            if j % n ==0:
                break
        else:
            print("分解结果：",i,j)
            break

aironeng

学习

mctcj

好耶

Hyjxsssss

# 题干
# 将一个给定的正偶数分拆成两个素数之和，则被称之为此数的哥德巴赫分拆。
# 循环打印直至非法输入

def judgeprime(index):
    storage = []
    for i in range(2, index):
        if index%i == 0:
            storage.append(i)
            break
    if len(storage) == 0:
        return True
    else:
        return False

while True:
    try:
        inputnumber = int(input('请输入一个取值在[4, 2333]区间的正偶数：'))
    except ValueError:
        print('非法输入！已结束程序！')
        break
    except KeyboardInterrupt:
        print('非法输入！已结束程序！')
        break
    else:
        if (inputnumber < 4) or (inputnumber % 2 == 1):
            print('非法输入！已结束程序！')
            break
        else:
            for left in range(2, inputnumber-1):
                right = inputnumber - left
                if left <= right:
                    if judgeprime(left) and judgeprime(right):
                        print('%d = %d + %d' % (inputnumber, left, right))

憨憨学py

pu-007

搜噶寺内

Alexiiis

沙发