19 - 素数的收官：哥德巴赫猜想
本帖最后由 不二如是 于 2022-6-27 18:10 编辑在线讲解：
https://www.bilibili.com/video/BV1HT4y1K7DY?p=22
经过前面 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 循环搞定：
**** Hidden Message *****
既然是验证，就不能像之前一样执行一次就结束，需要反复执行输出结果。
主框架还是用 while 循环，每输入一个数据就处理一次，直到人为结束程序或输入非法数据而终止输入：
if __name__ == "__main__":
while True:
print("请输入一个不小于4的正偶数：")
n = int(input())
guess(n)
if __name__ == '__main__' 的意思就是当 .py 文件被直接运行时，if __name__ == '__main__'之下的代码块将被运行。
好啦，这里执行下看结果：
源码：
核心代码都有了，完整代码留给你们当作业！
好了，下课！ 1 6666666666666 {:5_95:} 666 xueyixia {:10_254:} 膜 mod 学习学习
·1 把素数搞懂了一起就好办了！
even = int(input('请输入一个不小于4的正偶数：'))
for i in range(2,even):
for n in range(2,i):
ifi % n == 0:
break
else:
j = even - i
for n in range(2,j):
if j % n ==0:
break
else:
print("分解结果：",i,j)
break 学习 好耶 # 题干
# 将一个给定的正偶数分拆成两个素数之和，则被称之为此数的哥德巴赫分拆。
# 循环打印直至非法输入
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('请输入一个取值在区间的正偶数：'))
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)) {:10_266:} 搜噶寺内 沙发
页:
[1]