SRM524 Div1 Easy - MagicDiamonds

問題

自然数nを"素数でない自然数"の和で表すとき最小で何個の数が必要か

1 <= n <= 10^12

解法

nが3のときは3 (1+1+1)
そうじゃないときはnが素数なら2 (1 + (n-1))
nが素数じゃないなら1 (n)
∵ nとn-1が両方素数になるのはn=3のときだけだから

class MagicDiamonds {
public:
	// 素数判定 O(√N)
	bool isprime(ll n) {
		if (n==2) return 1;
		if (n<=1 || n%2==0) return 0;
		for (ll i=3; i*i<=n; i+=2) if (n%i==0) return 0;
		return 1;
	}

	ll minimalTransfer(ll n) {
		if (n==3) return 3;
		if (isprime(n)) return 2;
		return 1;
	}
};