[Codeforces] 735D. Taxes

題目連結:http://codeforces.com/problemset/problem/735/D

---

IOICamp的時候有提到這題，不過我其實已經忘了結論了www
去翻了一下才知道原來是跟哥德巴赫猜想有關，其猜想簡而言之就是說對於任意一個大於二的偶數，都可以拆成兩個質數相加。所以我們這題的做法就是先看看給定的數是不是質數，如果是當然就輸出1，接下來看他是不是偶數，是的話那根據歌德巴赫猜想，答案應該會是2，而對於一個奇數，我們要先看看他減二是不是質數，是的話輸出2，不是的話輸出3，因為對於一個奇數他一定是拆成一個質數加一個偶數，然後偶數拆成兩個質數，但要是拆出來的偶數是二，那答案就變成2了。
p.s. 附個維基上哥德巴赫猜想的條目https://zh.wikipedia.org/wiki/哥德巴赫猜想

#include <bits/stdc++.h>
using namespace std;
bool isprime(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0) return false;
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	if(isprime(n)) cout<<1<<'\n';
	else if(n%2==0 or isprime(n-2)) cout<<2<<"\n";
	else cout<<3<<'\n';
	return 0;
}