题解 | #查找组成一个偶数最接近的两个素数#

两种解法

（1）穷举所有小于n的素数，找出差值最小的一组

具体实现代码：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        // 找出1-n之间的所有质数
        List<Integer> prime = new ArrayList<>();
        boolean[] isPrime = new boolean[n+1];
        for (int i = 2; i<= n; i++) {
            if (!isPrime[i]) {
                prime.add(i);
            }
            for (int j = 0; j < prime.size(); j++) {
                if (prime.get(j) * i > n) {
                    break;
                }
                isPrime[i * prime.get(j)] = true;
                if (i % prime.get(j) == 0) {
                    break;
                }
            }
        }
        int min = Integer.MAX_VALUE;
        int ans1 = 0, ans2 = 0;
        for (int i = 0; i < prime.size(); i++) {
            int temp = n - prime.get(i);
            if (prime.contains(temp)) {
                int diff = Math.abs(temp - prime.get(i));
                if (min >= diff) {
                    min = diff;
                    ans1 = prime.get(i);
                    ans2 = temp;
                }
            }
        }
        min = Math.min(ans1, ans2);
        int max = Math.max(ans1, ans2);
        System.out.println(min);
        System.out.println(max);
    }
}

（2）从中间向两边扩展查找素数

从数字n中间位置开始往左右两边查找素数，因为一个偶数可以由两个素数组成，那么这两个素数必定是一个小于n/2，一个大于n/2情况。

那么从n/2位置，开始向左右两边查找第一次出现的素数，则这两个素数必定是差值最小的。

具体代码如下所示：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        // 从中间开始，向左右两边查找质数即可结束
        int mid = n / 2;
        int left = mid, right = mid;
        while (!isPrime(left) || !isPrime(right)) {
            left--;
            right++;
        }
        System.out.println(left);
        System.out.println(right);
    }
    public static boolean isPrime(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}