CodeForce 735D Taxes

将一个数拆解为尽量少的质数的和

题目大意

一个人的工资为n，他需要交n的最大质因数的税，若n为质数，则交的钱数为1。他为了逃税，将n分成n1,n2,n3…nn(都不为1)。将每一部分单独交税，问他想要让交的税最少，他需要将n分成几份？

题目解析

思路如下：将n分为最少数目的质数，比较这个数目跟最大质因数的大小。
理论上很难，但是，哥德巴赫猜想可以很好的解决这个问题。
任何一个大于2的偶数都可以分解为两个素数之和。
所以：
1.判断是否为偶数，偶数中如果是2输出1，否则输出2。不为偶数则继续
2.判断这个数字n是不是质数，是质数输出1，否则继续
3.判断n-2是不是质数，是质数输出2，否则n-3一定为偶数，3为质数，则输出3

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
bool isprime(int n)
{
        if(n==2||n==3)
        {
                return true;
        }
        for(int i=2;i<=sqrt(n);i++)
        {
                if(n%i==0)
                {
                        return false;
                }
        }
        return true;
}
int main()
{
        int n;
        cin>>n;
        if(n==2)
        {
                cout<<"1"<<endl;
                return 0;
        }
        if(n%2==0)
        {
                cout<<"2"<<endl;
        }
        else
        {
                if(isprime(n))
                {
                        cout<<"1"<<endl;
                }
                else if(isprime(n-2))
                {
                        cout<<"2"<<endl;
                }
                else
                {
                        cout<<"3"<<endl;
                }
        }
        return 0;
}