フェルマーテスト (paizaランク C 相当)

整数 N が素数であるかを高確率で判定する方法の 1 つとしてフェルマーテストがあります。
整数 N をフェルマーテストで素数判定するときの手順は次の通りです。

1. a を 2 から N-1 までの数からランダムに選ぶ。
2. N が a で割り切れる場合は N は素数でないと判定する。
3. a^(N-1) を N で割ったあまりが 1 ならば N は素数、1 でない場合は素数でないと判定する。

整数 N が与えられるので、 N が素数かどうかをフェルマーテストを用いて判定してください。
なお、今回の問題では、フェルマーテストの手順 1 の a は 2 で固定するものとします。
なお、「整数 N が素数である」とは「N が 1 でない、かつ、N の約数が 1 と N のみしか存在しない」ことをいいます。

---

ヒント
a^(N-1) を N で割ったあまりを求めるには、1 で初期化した変数 fermat を用意し、次の操作を N-1 回繰り返せば良いです。

1. fermat に a を掛ける。
2. fermat に 「fermat を N で割った余り」 を代入する。