题解 | #最少素数拆分#

最少素数拆分

http://www.nowcoder.com/practice/07d6df2014184decb329de777ba7ff51

题目描述
现在给定一个正整数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,内层循环为图片说明 ,因此总体的时间复杂度为图片说明 .
空间复杂度:没有引入额外的内存地址空间,因此空间复杂度为

方法二:数学的思想求解

求解思路
对于本问题的解决,我们亦可以采用数学逻辑思想进行求解。当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;
}
};

复杂度分析
时间复杂度:一层循环,因此时间复杂度为
空间复杂度:没有引入额外的内存地址空间,因此空间复杂度为

算法 文章被收录于专栏

算法题的题解以及感受

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-20 17:21
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-15 17:07
途虎_JAVA
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议