题目分析

1. 题目给出了我们一个偶数
2. 我们要将偶数拆成两个素数数字之和，这两个素数要求差值最小
3. 输出这两个素数

方法一：枚举

• 实现思路

  • 我们从1开始枚举到偶数n的一半，来找素数（对应的另一个数字就是偶数和当前枚举值的差值）

  • 假设拆成了两个数字为i，j

  • 我们要判断i和j是否都是素数，而且j-i的差值是否变得更小了

  • 直到我们找到最小的差值的时候，输出两个数字

def isPrime(n):                        # 判断是否为素数
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def solution(n):
    diff = n
    x = y = 0
    for i in range(1, n // 2 + 1):                        # i枚举从1开始找，直到n的一半
        j = n - i                                         # 对应的另一个值为 n-i
        if isPrime(i) and isPrime(j) and diff > i - j:    # 如果两者是素数且两素数之间更新了最小距离
            x, y = i, j
            diff = j - i
    print(x)
    print(y)
    return

while True:
    try:
        n = int(input())
        solution(n)
    except:
        break

复杂度分析

• 时间复杂度：$O(n\sqrt{n})O(n\backslash sqrt\{n\})$，采取枚举的方式的时间开销，枚举的每个数要进行素数判断，综合开销是$O(n\sqrt{n})O(n\backslash sqrt\{n\})$
• 空间复杂度：$O(1)O(1)$，只有了常数级别的空间开销

方法二：贪心枚举优化

• 实现思路
  • 我们可以直接采取从中间向两边枚举的方式，这样贪心的控制住两素数之差距离最小的这个限制
  • 并且我们可以直到偶数一定不是素数，因此每轮循环迭代都只要将步长设置为2即可
  • 这样我们只要迭代直到两个数都是素数即可输出
  • 但是我们要单独对偶数4的分解进行判断，偶数4的分解是唯一一个分解成两个素数2的用例；其他偶数分解的情况都是两个奇素数，因此单独抛出4来分情况

def isPrime(n):                        # 判断是否为素数
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def solution(n):
    if n == 4:                            # 单独对用例 4 进行判断输出，因为只有4的分解结果需要两个偶数2，其他情况分解都是奇数素数
        print(2)
        print(2)
        return
    i = n // 2
    l = i if i & 1 == 1 else i - 1        # 从中间开始往小方向找素数
    r = i if i & 1 == 1 else i + 1        # 从中间开始往大方向找素数
    while l > 0 and r < n:
        if isPrime(l) and isPrime(r):     # 如果两者都是素数则输出
            print(l)
            print(r)
            return
        else:                             # 否则迭代
            l -= 2
            r += 2
    return

while True:
    try:
        n = int(input())
        solution(n)
    except:
        break

复杂度分析

• 时间复杂度：$O(n\sqrt{n})O(n\backslash sqrt\{n\})$，采取枚举的方式嵌套素数判断部分总计的时间开销，但是在线性系数的级别上有优化
• 空间复杂度：$O(1)O(1)$，只有了常数级别的空间开销