题解 | #最少素数拆分#

思路

题目分析

1. 题目要求我们在给定正整数N的情况下，求出用素数相加得到N，所需要的最少的素数个数
2. 根据哥德巴赫猜想，大于2的偶数都可以拆分成两个素数之和（暂时未找到反例），所以我们可以直接用这个猜想。
3. 本题的关键在于，对于一个数字N，看似要找的素数的个数可以有很多个，但是经过数学推理，其实这个最少素数个数只能取值1,2,3

• 本题可以采用动态规划（方法一）的想法，将大问题N划分为其子问题，类似斐波那契数列的解决方案。我们假设最终返回的结果应该是f[N]，对于其子问题，我们可以遍历i = 2 to N/2，在其中取f[i] + f[N-i]的最小值作为最终结果。
• 本题也可以利用数学推导（方法二），在了解哥德巴赫猜想之后，数学推导了解到我们最终的返回结果只有1,2,3，从这个角度进行入手

方法一：动态规划（超空间）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断给定的正整数最少能表示成多少个素数的和
     * @param N int整型 给定的正整数
     * @return int整型
     */
    // 判断是否为素数
    int su(int num) {
        for(int i = 2; i <= sqrt(num); i++){
            int a = i;
            int b = num/i;
            if(a*b == num) return 0;                   //判断因数是否能重新乘回成为num
        }
        return 1;
    }

    int MinPrimeSum(int N) {
        // write code here
        vector<int> f(N+1, 9999);
        for(int i = 2; i <= N; i++) {
            if(su(i)) f[i] = 1;                        //如果当前数字i是素数则返回1
            else {
                for(int j = 2; j <= i/2; j++){
                    f[i] = min(f[i],f[j]+f[i-j]);      //如果i不是素数则将原数字拆成两个数字之和f[j]和f[i-j]，并从中取两者和最小的结果作为f[i]值
                }
            }
        }
        return f[N];                                
    }
};

复杂度分析

• 时间复杂度：，双重循环是的代价
• 空间复杂度：，利用了空间大小存储每一个数字的结果

方法二：数学推导（通过）

我们最终的情况只有三种，结果为1、2、3

1. 当N为素数时，返回1
2. 当N为大于2的偶数时，返回2
3. 当N为奇数时，如果N-2为素数，返回2
4. 其余情况返回3

关于情况三：N为奇数，在拆成两个数字的时候，必定一个是奇数一个是偶数，如果偶数拆出来是2，那么若N-2是素数则一定返回结果为2，若N-2不是素数则我们不拆2出来，我们按照情况四（下面的解释）拆奇数3出来。
关于情况四：N为奇数，在拆成两个数字的时候，必定一个是奇数一个是偶数，奇数我们可以固定是3（一个素数奇数），剩下的偶数必定可以分为两个素数的和，则最终结果一定是3。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断给定的正整数最少能表示成多少个素数的和
     * @param N int整型 给定的正整数
     * @return int整型
     */
    // 判断是否为素数
    int su(int num) {
        if(num < 2) return 0;
        for(int i = 2; i*i <= num; i++){
            if(num % i == 0) return 0;
        }
        return 1;
    }

    int MinPrimeSum(int N) {
        // write code here
        if(su(N)) return 1;        //当N为素数时，返回1
        if(N%2 == 0) return 2;     //当N为大于2的偶数时，返回2
        if(su(N-2)) return 2;      //当N为奇数时，如果N-2为素数，返回2
        return 3;                  //其余情况返回3
    }
};

复杂度分析

• 时间复杂度：，其中计算素数的时间为
• 空间复杂度：，未借助其他辅助空间