牛客题霸 最少素数拆分 C++题解/答案

题目描述

牛牛刚刚学习了素数的定义，现在给定一个正整数N，牛牛希望知道N最少表示成多少个素数的和。
素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

提示
哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。

题解：

结合哥德巴赫猜想，
如果N==2，它就是被自身素数构造的，答案是1
如果N>3&&N是偶合数（也就是大于2的偶数）时，根据猜想可以拆分成两个质数之和，所以答案是2
如果N>3&&N是奇合数时，奇合数=奇数+偶数
如果这个偶数是2&&我们只需要判断N-2是否为素数，这样答案是2
如果N-2不是素数，我们可以让奇合数=奇数+偶数中的奇数为素数，又因为偶数（此时不为2）答案是2，所以答案是3

代码：

class Solution {
   
public:
    /** * 判断给定的正整数最少能表示成多少个素数的和 * @param N int整型 给定的正整数 * @return int整型 */
    bool iff(int x)
    {
   
        if(x==1)return 0;
        if(x==2)return 1;
        for(int i=2;i<=sqrt(x);i++)
       if(x%i==0)return 0;
        
        return 1;
    }
    int MinPrimeSum(int N) {
   
        // write code here
        if(iff(N))return 1;
        if(N%2==0||iff(N-2))return 2;
        return 3;
    }
};