H-半素数 Semi-prime H-numbers

题意翻译

# 【问题描述】 形如$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$,第二个表示答案。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2046 [PDF](https://uva.onlinejudge.org/external/111/p11105.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11105/505fff7da40aa3d11f942713e5370d21326cd98a.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11105/b19c54035207d569de692453bc32d26fb8bde038.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11105/b64e631b78f538df029728e9e46bbd6739f013a7.png)

输入输出样例

输入样例 #1

21
85
789
0

输出样例 #1

21 0
85 5
789 62