最少素数拆分（847274）题解

暴力解法：
最暴力的做法是DFS枚举素数累加，但复杂度太大
根据哥德巴赫猜想，我们知道答案最大为3，因此可以先判断N本身是不是素数，然后暴力判断是否可以分解成两个素数的和，如果不行的话答案就是3。

bool IsPrime(int N) {
    if (N < 2) {
        return false;
    }
    for (int i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            return false;
        }
    }
    return true;
}
int MinPrimeSum(int N) {
    if (IsPrime(N)) {
        return 1;
    }
    for (int a = 2; N - a > 1; a++) {
        int b = N - a;
        if (IsPrime(a) && IsPrime(b)) {
            return 2;
        }
    }
    return 3;
}

正解：
当N > 3且N为偶合数时，N本身不是素数，根据哥德巴赫猜想，答案肯定为2
当N > 3且N为奇合数时，如果答案为2，因为N为奇数，因此只能拆解成奇数 + 偶数，而偶质数只有2，因此只需要判断N - 2是不是质数即可

bool IsPrime(int N) {
    if (N < 2) {
        return false;
    }
    for (int i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            return false;
        }
    }
    return true;
}

/**
 * 判断给定的正整数最少能表示成多少个素数的和
 * @param N int整型 给定的正整数
 * @return int整型
 */
int MinPrimeSum(int N) {
    if (IsPrime(N)) {
        return 1;
    }
    if (N % 2 == 0 || IsPrime(N - 2)) {
        return 2;
    }
    return 3;
}