SRM 524 easy:MagicDiamonds

SRM 524 の練習会に参加しました。easy だけしか解けなかったしそれも見事にひっかかって再提出しました。

問題

TopCoder Statistics - Problem Statement

解法

素数だったら (素数-1, 1) とやれば 2 回, 合成数だったら (その数字) で 1 回, というので基本的に良いですが例外的に n = 3 の場合だけは 3-1 = 2 が素数なので 3 回必要です。やられた。

bool prime(ll n) {
    if (n == 1) return false;
    for (ll i = 2; i*i <= n; i++) if (n%i == 0) return false;
    return true;
}

class MagicDiamonds {
public:
    long long minimalTransfer(long long n) {
        if (n == 3) return 3;
        if (prime(n)) return 2;
        return 1;
    }
};