题解 | #最少素数拆分#

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

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

方法一：暴力解法

求解思路
对于本题求解N最少能表示成多少个素数的和，想到使用DFS枚举素数累加，我们可以先判断N本身是不是素数，然后暴力判断N是否可以分解成两个素数的和，如果不能分解，则答案自然就是3.据此我们根据上述思路进行求解。

图片说明

解题代码

class Solution {
public:
bool IsPrime(int N) // 判断是否为素数
{
    if (N < 2)
    {
        return false;
    }
    for (int i = 2; i * i <= N; i++)
    {
        if (N % i == 0)
        {
            return false; // 不是素数，则返回false
        }
    }
    return true;
}
int MinPrimeSum(int N) {
    if (IsPrime(N)) // 判断是否为素数
    {
        return 1;
    }
    for (int i = 2; N - i > 1; i++) // 开始循环遍历
    {
        int j = N - i;
        if (IsPrime(i) && IsPrime(j)) 
        {
            return 2;
        }
    }
    return 3;
}
};

复杂度分析
时间复杂度：外层循环为N，内层循环为 $图片说明$ ，因此总体的时间复杂度为 $图片说明$ .
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：数学的思想求解

求解思路
对于本问题的解决，我们亦可以采用数学逻辑思想进行求解。当N>3且N为偶合数时，因为N本身不是素数，因此答案为2.当N>3且N为奇合数时，如果答案为2，因为N为奇数，因此只能拆解成奇数+偶数的形式，而偶质数只有2，所以只需判断N-2是不是质数即可。我们根据数学的思想，亦可得到本题的答案。

图片说明

解题代码

class Solution {
public:
bool IsPrime(int N)
{   //判断是否为质数
    if (N < 2)
    {
        return false;
    }
    for (int i = 2; i * i <= N; i++)
    {
        if (N % i == 0)
        {
            return false; // 取余为0，则不是质数
        }
    }
    return true;
}
int MinPrimeSum(int N) {
    if (IsPrime(N))
    {
        return 1;
    }
    if (N % 2 == 0 || IsPrime(N - 2))
    {
        return 2; // 数学的思想进行求解
    }
    return 3;
}
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(\sqrt{N})$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$