解题思路

  1. 题目要求：

    • 输入一个大于2的偶数
    • 找出差值最小的两个素数，使它们的和等于输入的偶数
    • 输出这两个素数（按从小到大顺序）

  2. 实现思路：

    • 判断一个数是否为素数
    • 从中间值向两边扩散查找
    • 找到第一对符合条件的素数即为所求

  3. 具体步骤：

    • 从 开始，分别向左右查找
    • 判断找到的数对是否都是素数
    • 如果都是素数且和为 ，则找到答案

代码

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    while (cin >> n) {
        // 从中间向两边查找
        int mid = n / 2;
        for (int i = 0; i <= mid; i++) {
            if (isPrime(mid - i) && isPrime(mid + i)) {
                cout << mid - i << endl << mid + i << endl;
                break;
            }
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            // 从中间向两边查找
            int mid = n / 2;
            for (int i = 0; i <= mid; i++) {
                if (isPrime(mid - i) && isPrime(mid + i)) {
                    System.out.println(mid - i);
                    System.out.println(mid + i);
                    break;
                }
            }
        }
    }
}

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

while True:
    try:
        n = int(input())
        # 从中间向两边查找
        mid = n // 2
        for i in range(mid + 1):
            if is_prime(mid - i) and is_prime(mid + i):
                print(mid - i)
                print(mid + i)
                break
    except EOFError:
        break

算法及复杂度

  • 算法：中心扩散法
  • 时间复杂度： - 每次判断素数需要，最多需要检查对数
  • 空间复杂度： - 只使用常数额外空间