AT1476 素数判定

    • 774通过
    • 2.9K提交
  • 题目来源 AtCoder 1476
  • 评测方式 RemoteJudge
  • 标签 枚举,暴力 素数判断,质数,筛法
  • 难度 入门难度
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    如果 n 是素数, n 是素数。 如果N是一个合数且N既不是偶数也不是5的倍数,并且如果每个数字的和不能被3整除,则N是类似素数的 否则, n 不是素数

    类似素数的和素数都输出“Prime” 否则输出“Not Prime”

    感谢@LW_h_FP 提供的翻译

    题目描述

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

    $ 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 $ は素数でも合成数でもないので、「素数っぽくない」と判定されます。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。