思路：

题目的主要信息：

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

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

$r e s = 1$ ，N本身就是素数
$r e s = 2$ ，N是一个大于2的偶数，或者N是一个奇合数
$r e s = 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(n^{3/2})$ ，查看n是否是质数最多为 $\sqrt n$ ，因此这里是 $\sqrt 2 + \sqrt 3 + ... + \sqrt n = 2/3*n^{3/2} -1$ ，因此查看所有的isPrime函数需要 $O(n^{3/2})$
空间复杂度： $O (1)$ ，无额外空间使用

方法二：数学

具体做法： 对于素数和偶数我们都非常好判断，但是对于奇合数我们需要再变化一下，我们都是到奇合数 $N$ ，那么 $N - 3$ 一定为偶数，则有 $2 < = f (N) < = f (N - 3) + 1 = 3$ ，如果 $f (N) = 2$ , 如： $N = a + b$ ，则 $a$ 与 $b$ 不可能是既是两个奇数，又是两个素数， $a$ 与 $b$ 必有一个是 $2$ ，否则 $N$ 就是偶数，矛盾。因此我们可以有如下结论：如果 $N - 2$ 是素数， $f (N) = 2$ ，否则， $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(\sqrt n)$ ，最坏情况判断是否是素数，遍历全部
空间复杂度： $O (1)$ ，无额外空间使用

题解 | #最少素数拆分#

思路：

方法一：暴力法（超时）

方法二：数学