[ARC044A] 素数判定
题意翻译
如果 $n$ 是素数, $n$ 是素数。 如果 $N$ 是一个合数且 $N$ 既不是偶数也不是 $5$ 的倍数,并且如果每个数字的和不能被 $3$ 整除,则 $N$ 是类似素数的 否则, $n$ 不是素数
类似素数的和素数都输出`Prime` 否则输出`Not Prime`。
题目描述
[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修正)
输入输出样例
输入样例 #1
42
输出样例 #1
Not Prime
输入样例 #2
49
输出样例 #2
Prime
输入样例 #3
3
输出样例 #3
Prime
输入样例 #4
1
输出样例 #4
Not Prime
说明
### Sample Explanation 1
$ 42 $は合成数かつ$ 1 $の位が偶数なので、「素数っぽくない」と判定されます。
### Sample Explanation 2
$ 49 $は素数ではありませんが、「素数っぽい」と判定されます。
### Sample Explanation 3
$ 3 $は素数なので、「素数っぽい」と判定されます。
### Sample Explanation 4
$ 1 $は素数でも合成数でもないので、「素数っぽくない」と判定されます。