FreedomLy's blog.

【每周一坑】验证哥德巴赫猜想

字数统计: 393阅读时长: 1 min
2017/05/28 Share

Goldbach's conjecture

哥德巴赫在1742年给欧拉的信中提出了以下猜想:任一大于2的整数都可以写成三个质数之和。(因现今数学界已经不再使用“1也是质数”这个约定,原初猜想的现在陈述为:任一大于5的整数都可以写成三个质数之和。)欧拉在回信中也提出另一个等价的版本,即任一大于2的偶数都可以写成两个质数之和。今日常见的猜想陈述为欧拉的版本。

问题描述

本周题目

实现一段代码,输入一个大于2的偶数k,输出两个质数m、n,满足 m + n == k。

示例:

1
2
3
4
>>> Goldbach(123456)
7 123449
>>> Goldbach(12345678)
31 12345647

思路

这个问题其实就是在求k范围内的质数的基础上,在加一个判断,使得两个质数之和等于k即可。要注意的是,求得的解并不唯一。

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
25
26
27
28
29
30
import math

# 求得小于等于n的所有质数
def get_prime(n):
prime = []
prime_dic = {}
for i in range(2, n+1):
prime_dic[i] = 1
for i in range(2, int(math.sqrt(n)) + 1):
for j in range(i * i, n + 1, i):
if prime_dic[i] == 1:
prime_dic[j] = 0
for k, v in prime.items():
if v == 1:
prime.append(k)
return prime

# 求满足猜想的质数和
def gold_bach(n):
cnt = 0
prime = get_prime(n)
for prime1 in prime:
prime2 = n - prime1
if prime2 in prime and cnt != 1: # 只输出一种结果
cnt += 1
return prime1. prime2

if __name__ == '__main__'
print(gold_bach(123456))
print(gold_bach(12345678))

输出结果

print(gold_bach(123456))

(7, 123449)

print(gold_bach(12345678))

(31, 12345647)

与示例一致。

End~


CATALOG
  1. 1. 问题描述
  2. 2. 思路
  3. 3. Python实现
  4. 4. 输出结果