← 返回题目列表

AtCoder · arc044_a

A. 素数测试

中文机器翻译题面 查看原题

問題文

Takahashi 喜欢素性测试算法。我每天都会实现并尝试各种素性测试算法。 然而,高桥太过于尝试测试素数,以至于他厌倦了测试素数。 因此,高桥先生决定确定这个数字是否看起来像素数。 大于或等于

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既不是素数,也不是合数,因此判断为“不像素数”。