SRM524 Div2 Medium MagicDiamonds

問題

n個の荷物を目的地まで送りたい.任意のxを送ろうと思ったら魔法を送って一回で送れる.但し,xが素数だった場合荷物は消滅する.最小回数で"n個"の荷物を送りたい(消滅させてはいけない)

解答

nが素数だった場合1回で送れないが,n-1, 1と2回で送れる.nは素数なのでn-1は偶数=素数ではない.

class MagicDiamonds {
public:
  long long minimalTransfer(long long n) {
    if (n == 1)return 1;
    if (n == 2)return 2;
    for (long i = 3; i*i <= n; i+=2){
      if(n % i == 0) return 1;
    }
    return 2;
  }