最少素数拆分

class Solution {
public:
    /**
     * 判断给定的正整数最少能表示成多少个素数的和
     * @param N int整型 给定的正整数
     * @return int整型
     */
    bool isPrime(int n){
        if(n==1)
            return false;
        if(n==2)
            return true;
        for(int i=2;i*i<=n;i++)
            if(n%i==0)
                return false;
        return true;
    }
    int MinPrimeSum(int N) {
        if(N<=1)
            return 0;
        if(N&1){
            if(isPrime(N))
                return 1;
            else{
                if(isPrime(N-2))
                    return 2;
                else
                    return 3;
            }
        }else{
            if(N==2)
                return 1;
            else
                return 2;
        }
    }
};

网络问题无法提交 一直在转圈，让我以为写了个死循环，改了好几次，后来用的手机热点

func MinPrimeSum(N int) int {
    res := 0
    if N == 0 || N == 1 {
        return res
    }
    if N%2 == 0 {
        if N == 2 {
            res = 1
        } else {
            res = 2
        }
    } else {
        if isSU(N) {
            res = 1
        } else {
            if isSU(N - 2) {
                res = 2
            } else {
                res = 3
            }

        }
    }
    return res
}
func isSU(n int) bool {
    for i := 2; i < n; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

import java.util.*;


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

(1).如果N是素数，则返回1，否则进入(2)；

(2).如果N为偶数，N==2 ，返回1，N != 2，返回2 （哥德巴赫猜想）。否则进入(3)；

(3)N为奇数，分解为p=(p-2)+2：

若p-2为质数，则可表示为两个质数的和
若p-2为非质数，则可表示为三个质数的和

需要注意的是，在判断质数函数中，采用平方根可减小整个算法的时间复杂度，否则算法的时间复杂度会超标！

#
# 判断给定的正整数最少能表示成多少个素数的和
# @param N int整型 给定的正整数
# @return int整型
#
class Solution:
    def MinPrimeSum(self , N ):
        # write code here
        ret = 0
        if(N%2 == 0):
            if(N==2):
                ret = 1
            else:
                ret = 2
        else:
            if(self.isPrimeNumber(N)):
                ret =  1
            elif(self.isPrimeNumber(N-2)):
                ret = 2
            else:
                ret = 3
        return ret
    def isPrimeNumber(self,x):
        import math
        flag = True
        if(x==1):
            flag = False
        for i in range(2,int(math.sqrt(x))+1):
            if(x%i==0):
                flag=False
        return flag

跟上面车站建造问题一样
class Solution {
public:
	int MinPrimeSum(int N) {
		if (is_prime(N))        //判断是否为素数
			return 1;
		else
		{
			if (N % 2 == 0)    //判断是否为偶数
				return 2;
			else
			{
				if (is_prime(N - 2))    //判断n-2是否为素数
					return 2;
				else
					return 3;
			}
		}
	}

	bool is_prime(int n)
	{
		for (int i = 2; i <= sqrt(n); i++)
			if (n % i == 0)
				return false;
		return true;
	}
};

/*
分类讨论：
1. 对于质数：返回1
2. 对于偶数（大于等于4），根据哥德巴赫猜想，都可以分解为两个质数的和，返回2
3. 对于非质数的奇数：如果该奇数-2为质数，返回2；否则返回3

*/

class Solution {
public:
    /**
     * 判断给定的正整数最少能表示成多少个素数的和
     * @param N int整型 给定的正整数
     * @return int整型
     */
    int MinPrimeSum(int N) {
        // write code here
        int i;
        bool flag1 = 0, flag2 = 0;
        if(N == 2) {
            return 1;
        }
        else if(N%2 == 0) {
            return 2;
        }
        for(i = 3; i*i <= N; i = i + 2) {
            if(N%i == 0) {
                flag1 = 1;
            }
            if((N-2)%i == 0) {
                flag2 = 1;
            }
        }
        
        if(flag1 == 0) {
            return 1;
        }
        else if(flag1 == 1 && flag2 == 0) {
            return 2;
        }
        else {
            return 3;
        }
    }
};