SRM524 Div1 Easy - MagicDiamonds
解法
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; } };