AT_arc044_a [ARC044A] 素数判定

[problemUrl]: https://atcoder.jp/contests/arc044/tasks/arc044_a 高橋君は素数判定アルゴリズムが大好きです。毎日さまざまな素数判定アルゴリズムを実装して遊んでいます。 しかし、高橋君は素数判定をしすぎてしまったので、素数判定に飽きてしまいました。 そこで高橋君は、「素数っぽく見える数」判定をすることにしました。 $ 1 $以上の整数$ N $は、以下のように「素数っぽい」かどうかが判定されます。 - $ N $が素数であるなら、$ N $は「素数っぽい」 - $ N $が合成数であるなら、$ N $を$ 10 $進表記した時の$ 1 $の位が偶数でも$ 5 $でもなく、各桁の和が$ 3 $で割り切れないならば、$ N $は「素数っぽい」 - それ以外の場合、$ N $は「素数っぽくない」 整数$ N $が与えられるので、$ N $が「素数っぽい」場合は"Prime"、そうでない場合は"Not Prime"と出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ - $ 1 $ 行目には、整数$ N(1\ ≦\ N\ ≦\ 10^9) $が与えられる。

$ N $が「素数っぽい」場合は"Prime"、そうでない場合は"Not Prime"と出力せよ。 出力の末尾に改行を入れること。(21:40修正)

### Sample Explanation 1 $ 42 $は合成数かつ$ 1 $の位が偶数なので、「素数っぽくない」と判定されます。 ### Sample Explanation 2 $ 49 $は素数ではありませんが、「素数っぽい」と判定されます。 ### Sample Explanation 3 $ 3 $は素数なので、「素数っぽい」と判定されます。 ### Sample Explanation 4 $ 1 $は素数でも合成数でもないので、「素数っぽくない」と判定されます。