CF735D Taxes

传送门

一道比较有意思的数学题。

首先，根据贪心的原理，最好把 $n$ 全部分成质数。

考虑分类讨论，

1. $n==1$ 或 $n==2$ ，显然答案是 $1$

2. $n>2$ 且 $n$ 为偶数，也就是 $n \geq 4$ ，由哥德巴赫猜想，发现 $n$ 可以分成两个质数之和，所以答案为 $2$

3. $n>2$ 且 $n$ 为奇数，

还是分成两种情况：

a. $n$ 为质数，答案为 $1$ ，

b. $n$ 不为质数，发现 $n$ 至少为 $9$ ，这样比较好办，先从 $n$ 里面分出一个 $3$ ，剩下的由哥德巴赫猜想可以分成两个质数，答案为 $3$

在具体实现时，发现有更简洁的写法：

1
2
3

if (isprime(n)) p(1);
else if (n%2==0||isprime(n-2)) p(2);
else p(3);

也就是把很多情况合起来写罢了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define p(a) printf("%d\n",a)
using namespace std;
inline bool isprime(register int x){
    for (register int i=2;i*i<=x;++i){
        if (x%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int n;
    scanf("%d",&n);
    if (isprime(n)) p(1);
    else if (n%2==0||isprime(n-2)) p(2);
    else p(3);
}