A - 素数判定 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は素数判定アルゴリズムが大好きです。毎日さまざまな素数判定アルゴリズムを実装して遊んでいます。 しかし、高橋君は素数判定をしすぎてしまったので、素数判定に飽きてしまいました。 そこで高橋君は、「素数っぽく見える数」判定をすることにしました。

1以上の整数Nは、以下のように「素数っぽい」かどうかが判定されます。

  • Nが素数であるなら、Nは「素数っぽい」
  • Nが合成数であるなら、N10進表記した時の1の位が偶数でも5でもなく、各桁の和が3で割り切れないならば、Nは「素数っぽい」
  • それ以外の場合、Nは「素数っぽくない」

整数Nが与えられるので、Nが「素数っぽい」場合は"Prime"、そうでない場合は"Not Prime"と出力してください。


入力

入力は以下の形式で標準入力から与えられる。

N
  • 1 行目には、整数N(1 ≦ N ≦ 10^9)が与えられる。

出力

Nが「素数っぽい」場合は"Prime"、そうでない場合は"Not Prime"と出力せよ。

出力の末尾に改行を入れること。(21:40修正)

入力例1

42

出力例1

Not Prime

42は合成数かつ1の位が偶数なので、「素数っぽくない」と判定されます。


入力例2

49

出力例2

Prime

49は素数ではありませんが、「素数っぽい」と判定されます。


入力例3

3

出力例3

Prime

3は素数なので、「素数っぽい」と判定されます。


入力例4

1

出力例4

Not Prime

1は素数でも合成数でもないので、「素数っぽくない」と判定されます。