描述

题目描述

任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对。

示例

输入：
20
输出：
7
13

知识点：穷举，贪心，数组，基础数学

难度：⭐⭐⭐

题解

方法一：穷举

解题思路：

对于一个数字，我们可以从2遍历到n，寻找两个加数都是素数的情况，然后比较素数之间的差值，把要输出的变量更新为更小的差值及这两个变量，最后枚举完得到就是差值最小的两个素数。

算法流程：

• 从2开始穷举，直到num
• 如果 isPrime(i) && isPrime(num - i)判断是否素数后，保存两数之差最小的两个元素

Java 版本代码如下：

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int num = scanner.nextInt();
        	solution(num);
        }
    }

    private static void solution(int num) {
        int min = Integer.MAX_VALUE;
        int[] res = new int[2];
        // 从2开始穷举
        for(int i = 2; i < num; i++) {
            if(isPrime(i) && isPrime(num - i)) {
                // 保存最接近的两个素数
                if(Math.abs(num - i - i) < min) {
                    res[0] = i;
                    res[1] = num - i;
                    min = Math.abs(num - i - i);
                }
            }
        }
        System.out.println(res[0] + "\n" + res[1]);
    }
    // 判断是否素数
    private static boolean isPrime(int num) {
        for(int i = 2; i <= Math.sqrt(num); i++) {
            if(num % i == 0) {
                return false;
            }
        } 
        return true;
    }
}

复杂度分析：

时间复杂度：$N\sqrt{N}N\backslash sqrt\{N\}$，外循环遍历N次，内循环遍历$\sqrt{N}\backslash sqrt\{N\}$

空间复杂度：O(1)，无需用到额外空间

方法二：穷举优化

图解：

解题思路：

采取从中间向两边枚举的方式，这样贪心的控制住两素数之差距离最小的这个限制

算法流程：

• 对于每个数字，从最接近的两个中位数开始处理判断是否素数
• 如果两个组成偶数的数字都是素数，因为是从最接近的两个数开始枚举，因此一旦都是素数则输出并返回，得到结果

Java 版本代码如下：

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int num = scanner.nextInt();
        	solution(num);
        }
    }

    private static void solution(int num) {
        //如num=10, 遍历:5,6,7,8
        // 从最接近的两个中位数开始处理判断
        for(int i = num / 2; i < num - 1; i++) {
            if(isPrime(i) && isPrime(num - i)) {
                System.out.println((num - i) + "\n" + i);
                return;
            }
        }
    }
    // 判断是否素数
    private static boolean isPrime(int num) {
        for(int i = 2; i <= Math.sqrt(num); i++) {
            if(num % i == 0) {
                return false;
            }
        } 
        return true;
    }
}

复杂度分析：

时间复杂度：$N\sqrt{N}N\backslash sqrt\{N\}$，外循环最多遍历 N/2 次，内循环每个数最多是$\sqrt{N}\backslash sqrt\{N\}$

空间复杂度：O(1)，只用到常数级别的空间开销