NC527 最少素数拆分（四种语言+视频讲解）

- 题目描述：

- 题目链接：

https://www.nowcoder.com/practice/07d6df2014184decb329de777ba7ff51?tpId=196&&tqId=37215&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total/question-ranking
- 设计思想：

-视频讲解链接B站视频讲解
- 复杂度分析：

- 代码：
c++版本:

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

Java版本：

import java.util.*;


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

Python版本:

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断给定的正整数最少能表示成多少个素数的和
# @param N int整型 给定的正整数
# @return int整型
#
import math
class Solution:
    def isprime(self,N):
        if(N < 2):return False
        for i in range(2,int(math.sqrt(N))+1):
            if N % i == 0:
                return False
        return True
    def MinPrimeSum(self , N ):
        # write code here
        res=0
        if(self.isprime(N)):
            return 1
        if N % 2 == 0 or self.isprime(N - 2):
            return 2;
        return 3;

JavaScript版本:

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