CodeForces - 735D Taxes

     题意：一个人交税要交他收入的最大公因数，但是它可以把工资拆分为任意的几部分，交每一部分的最大公因数，但是不能拆分为1      思路：如果工资为素数就交税为1，显然我们需要要把这个数拆为素数尽可能的多，任意一个偶数可以表示为两个素数的和，所以偶数交税为2，然后只剩下不是素数的奇数了，我是这样处理的，从n-2开始（因为不能拆为1），找到离n最近的一个素数，然后递归的处理n-最近的这个素数     #include<iostream> #include<cmath> using namespace std; bool isPrime(long long n) { for(int i=2;i<=sqrt(n);i++) if(n%i==0) return false; return true; } int solve(long long n) { if(isPrime(n)) return 1; else if(n%2==0) return 2; else { for(int i=n-2;i>=2;i--) { if(isPrime(i)) { //cout<<i; return 1+solve(n-i); break; } } } } int main(void) { long long n; cin>>n; int ans=solve(n); cout<<ans<<endl; return 0; }