最少素数_正整数最少分解成几个质数的和

题目描述
小X刚刚学习了素数的定义，现在给定一个正整数N，小X希望知道N最少表示成多少个素数的和。
素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

提示
哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。
输入
输入一个正整数n（n<=1e9）。多组输入。
输出
组成n的素数个数。
样例输入 Copy
3
6
样例输出 Copy
1
2
提示

3本身就是1个素数。

6可以表示为3 + 3，注意同样的素数可以使用多次。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int f(int t){
for(int i=2;i<=sqrt(t+1);i++){
    if(t%i==0){return -1;break;}
}
return 1;
}
int main()
{

    int n;

    while(~scanf("%d",&n)){
            if(n==1){printf("0\n");}
        else if(n==2){printf("1\n");}
        else if(f(n)==1){printf("1\n");}
        else if(n%2==0||f(n-2)==1)
                    {printf("2\n");}

        else{printf("3\n");}

    }
    return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28