题解 | #最少素数拆分#

最少素数拆分

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

思路：

题目的主要信息：
题目比较简短，需要注意的是哥德巴赫猜想，任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。

已知的信息有一个整数N，需要计算N能表示为多少个素数的和，并返回个数
需要注意的是2是唯一的偶质数

方法一：数学方法

首先判断N是否为素数，分为两种情况：
a.N为素数，N不能拆分为两个数相加，因此只能表示为1个素数的和，这个素数就是它本身，返回1。
b.N不为素数，又分为两种情况：
-1.若N为偶数，根据哥德巴赫猜想，任意大于2的偶数都可以拆分成两个质数之和。因此能表示为2个素数的和，返回2。
-2.若N为奇数，由于奇数=奇数+偶数，偶数有素数偶数和非素数偶数，素数偶数只有2。首先考虑N-2是否为素数，如果N-2为素数，则N可以表示为 $图片说明$ ；若N-2不为素数，因为N为奇数，奇数=奇数+偶数，素数偶数2已经在N-2为素数时考虑过了，现在考虑非素数偶数+素数奇数，非素数偶数可以表示为两个素数之和，因此能表示为三个素数相加，返回3。
判断流程如下图所示
图片说明
具体做法：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断给定的正整数最少能表示成多少个素数的和
     * @param N int整型 给定的正整数
     * @return int整型
     */
    bool IsPrimeNum(int M){
        int flag=0;
        for(int i=2;i<M;i++)
        {
            if(M%i==0){
                return false;
            }
        }
        return true;
    }
    int MinPrimeSum(int N) {
        // write code here
        //判断N是否为素数
        if(IsPrimeNum(N))
        {
            return 1;
        }
        //若N不为素数
       if(N%2==0)//若N不为素数，但为偶数时
       {
           return 2;
       }else{
           if(IsPrimeNum(N-2))//若N不为素数，也不为偶数，且N-2为素数时，N=（N-2）+2
           {
               return 2;
           }else{//若N不为素数，也不为偶数，且N-2为奇合数时
               return 3;
           }
       }
    }
};

复杂度分析：

时间复杂度： $图片说明$ ,在判断某个数是否为素数的时候需要遍历一遍。
空间复杂度： $图片说明$ ,在本解法中只用到了i、flag等常数空间。

方法二：暴力遍历

根据题目意思，有三种可能的结果：
若N为素数，不能被拆分成素数之和，因此返回1；
若N为合数，可能拆分成三个素数之和，也可能拆分为两个素数之和；
因此，先判断N是否为素数，若为素数则返回1；若N为合数，遍历一遍所有可能两个数相加为N的可能，如果存在两个数都为素数的情况，则说明N可以表示为两个素数相加，返回2；若N不能表示为连个素数相加，只剩最后一种情况，返回3；
方法二和方法一判断是否为素数的方法是一样的。
具体做法：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断给定的正整数最少能表示成多少个素数的和
     * @param N int整型 给定的正整数
     * @return int整型
     */
    bool IsPrimeNum(int M){
        int flag=0;
        for(int i=2;i<M;i++)
        {
            if(M%i==0){
                return false;
            }
        }
        return true;
    }
    int MinPrimeSum(int N) {
        // write code here
        //判断N是否为素数
        if(IsPrimeNum(N))
        {
            return 1;
        }
        //若N不为素数
        int mid=N/2+1;
        for(int i=2;i<mid;i++)
        {
            if(IsPrimeNum(i)&&IsPrimeNum(N-i))
            {
                return 2;
            }
        }
        return 3;
    }
};

复杂度分析：