思路：

题目的主要信息：

• 求一个整数N最少能够被拆分为多少个素数相加
• 哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和

根据哥德巴赫猜想，我们的结果res只会有三种情况：

• $res=1res\; =\; 1$res=1，N本身就是素数
• $res=2res\; =\; 2$res=2，N是一个大于2的偶数，或者N是一个奇合数
• $res=3res\; =\; 3$res=3，N是一个大于2的奇数且不为素数，则N-3为偶数，偶数的两个数加上3最多三个数

可以看到，奇合数有两种情况。

方法一：暴力法（超时）

具体做法： 首先我们判断N是否为素数，是则返回1，然后我们从2遍历到N的一半，查看相加为N的两个数是否素数，如果是则返回2，否则返回3.

class Solution {
public:
    bool isPrime(int n){ //判断是否是素数
         for(int i = 2; i <= (int) sqrt(n); i++){
            if(n % i == 0)
                return false;
        }
        return true;
    }
    int MinPrimeSum(int N) {
        if(isPrime(N)) //本身就是素数
            return 1;
        for(int i = 2; i < N / 2 + 1; i++){
            if(isPrime(i) && isPrime(N - i)) //能找到两个和为素数
                return 2;
        }
        return 3;  //最大为3
    }
};

复杂度分析：

• 时间复杂度：$O\left(n^{3/2}\right)O(n^\{3/2\})$O(n3/2)，查看n是否是质数最多为$\sqrt{n}\backslash sqrt\; n$n​，因此这里是$\sqrt{2}+\sqrt{3}+...+\sqrt{n}=2/3\ast n^{3/2}-1\backslash sqrt\; 2\; +\; \backslash sqrt\; 3\; +\; ...\; +\; \backslash sqrt\; n\; =\; 2/3*n^\{3/2\}\; -1$2​+3​+...+n​=2/3∗n3/2−1，因此查看所有的isPrime函数需要$O\left(n^{3/2}\right)O(n^\{3/2\})$O(n3/2)
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用

方法二：数学

具体做法： 对于素数和偶数我们都非常好判断，但是对于奇合数我们需要再变化一下，我们都是到奇合数$NN$N，那么$N-3N-3$N−3一定为偶数，则有2<=f(N)<=f(N−3)+1=3，如果$f\left(N\right)=2f(N)=2$f(N)=2, 如：$N=a+bN=a+b$N=a+b，则$aa$a与$bb$b不可能是既是两个奇数，又是两个素数，$aa$a与$bb$b必有一个是$22$2，否则$NN$N就是偶数，矛盾。 因此我们可以有如下结论：如果$N-2N-2$N−2是素数，$f\left(N\right)=2f(N)=2$f(N)=2，否则，$f\left(N\right)=3f(N)=3$f(N)=3。

class Solution {
public:
    bool isPrime(int n){ //判断是否是素数
         for(int i = 2; i <= (int) sqrt(n); i++){
            if(n % i == 0)
                return false;
        }
        return true;
    }
    int MinPrimeSum(int N) {
        if(isPrime(N)) //本身就是素数
            return 1;
        if(N % 2 == 0) //偶数
            return 2;
        if(isPrime(N - 2)) //奇合数的两种情况
            return 2;
        return 3;  //最大为3
    }
};

复杂度分析：

• 时间复杂度：$O\left(\sqrt{n}\right)O(\backslash sqrt\; n)$O(n​)，最坏情况判断是否是素数，遍历全部
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用