UVA11105 H-半素数 Semi-prime H-numbers

    • 45通过
    • 91提交
  • 题目来源 UVA 11105
  • 评测方式 RemoteJudge
  • 标签 同余,中国剩余定理 枚举,暴力 素数判断,质数,筛法
  • 难度 提高+/省选-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    本题征求翻译。如果你能提供翻译或者题意简述,请 提交翻译 ,感谢你的贡献。

    题意翻译

    【问题描述】

    形如$4n+1$的数被称为“H数”,乘法在“H数”组成的集合内是封闭的。在这个集合中只能被1和本身整除的数叫做“H-素数”(不包括1),其余的数被称为“H-合数”。一个“H-合成数”是一个能且只能分解成两个“H-素数”乘积的“H-合数”(可能有多种分解方案)。比如$441=21*21=9*49$,所以$441$是“H-合成数”。$125=5*5*5$,所以125不是“H-合成数”。

    求$0$~$h$范围内“H-合成数”的个数。

    【输入格式】

    输入若干行,每行一个小于等于$1000001$的整数$h$,一个$0$表示结束。

    【输出格式】

    对于每一行输入,输出两个数,第一个表示当前的$h$,第二个表示答案。

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    输入样例#1: 复制
    21
    85
    789
    0
    输出样例#1: 复制
    21 0
    85 5
    789 62
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。