题解 | #最少素数拆分#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 判断给定的正整数最少能表示成多少个素数的和
 * @param N int整型 给定的正整数
 * @return int整型
 */
int isPrime(int N){
    if(N<2){
        return 0;
    }
    for(int i=2;i<=sqrt(N);i++){
       if(N%i==0){
           return 0;
       } 
    }
     return 1;
}
int MinPrimeSum(int N ) {
    // write code here
    
    if(isPrime(N)){//素数本身
        return 1;
    }
    if(N%2==0||isPrime(N-2)){//若B为偶数则一定可以拆分为两个质数合，
                             //N为奇数时，奇数=奇数+偶数，而偶质数只有2，所以另一个数必为质数（N-2）
        return 2;
    }
    return 3;
//     for(int a=2;a<N/2;a++){//哥德巴赫猜想
//         int b=N-a;
//         if(isPrime(a)&&isPrime(b)){
//             return 2;
//         }
//     }
    return 3;
}