哥德巴赫猜想验证器 - 编程实现及字典序最小解法 - 常规

哥德巴赫猜想验证器 - 编程实现及字典序最小解法

哥德巴赫猜想：任何一个大于 6 的偶数总可以分解为两个素数之和。现在，请你编程验证哥德巴赫猜想，即输入一个大于 6 的偶数 n ，将其分解为两个素数之和输出。如果有多种分解答案，请输出字典序最小的那一个。

输入描述

一行一个正整数 n 。

输出描述

一行一个表达式，表示字典序最小的一种分解方法，具体格式参见样例。

用例输入 1

6 用例输出 1

6=3+3 用例输入 2

14 用例输出 2

14=3+11

实现思路

对于给定的偶数n，我们可以从2开始遍历到n/2，判断每一个数是否为素数。如果找到一个素数p，那么n-p也一定是素数，因为如果n-p是合数，那么它一定可以分解成两个数的乘积，而这两个数的和就是n，与哥德巴赫猜想相矛盾。

根据题目要求，我们需要输出字典序最小的分解方法。所以我们可以从2开始遍历，找到第一个素数p，然后判断n-p是否也是素数。如果是素数，那么输出分解结果，如果不是，继续遍历下一个素数。

代码实现 (Python)

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

n = int(input())
for p in range(2, n):
    if is_prime(p) and is_prime(n - p):
        print(f'{n}={p}+{n-p}')
        break

代码解释

is_prime(num) 函数：
- 判断一个数是否为素数。
- 如果 num 小于 2，则返回 False。
- 遍历从 2 到 num 的平方根的所有数 i，如果 num 能被 i 整除，则返回 False。
- 如果遍历完所有数都没有被整除，则返回 True，表示 num 是素数。
主程序部分
- 输入偶数 n。
- 遍历从 2 到 n 的所有数 p。
- 如果 p 和 n-p 都是素数，则输出 n 的分解结果，并退出循环。

示例输出

对于输入样例6，输出结果为：

6=3+3

对于输入样例14，输出结果为：

14=3+11