A - 素数判定
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は素数判定アルゴリズムが大好きです。毎日さまざまな素数判定アルゴリズムを実装して遊んでいます。 しかし、高橋君は素数判定をしすぎてしまったので、素数判定に飽きてしまいました。 そこで高橋君は、「素数っぽく見える数」判定をすることにしました。
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修正)入力例1
42
出力例1
Not Prime
42は合成数かつ1の位が偶数なので、「素数っぽくない」と判定されます。
入力例2
49
出力例2
Prime
49は素数ではありませんが、「素数っぽい」と判定されます。
入力例3
3
出力例3
Prime
3は素数なので、「素数っぽい」と判定されます。
入力例4
1
出力例4
Not Prime
1は素数でも合成数でもないので、「素数っぽくない」と判定されます。