问题描述

问题描述
一个H-number是所有的模四余一的数。

如果一个H-number是H-primes 当且仅当它的因数只有1和它本身（除1外）。

一个H-number是H-semi-prime当且仅当它只由两个H-primes的乘积表示。

H-number剩下其他的数均为H-composite。

给你一个数h,问1到h有多少个H-semi-prime数。

思路分析

一个和素数相关的题目，二重循环进行打表，注意这里的复杂度并不是$O(n^2)$，可以对复杂度进行一个简单的估算，

i=5, j=5...200000 运算次数 50000
...
i=85, j=5...11764 运算次数 2941
可以看到随着i的增大，j循环的次数迅速减小，最终一定不会超过1000w的量级。

还有一点需要注意，i和j必须都是从5开始，我一开始想的是

	for (ll i = 5; i < MAX; i += 4) {for (ll j = i; j<MAX; j += 4) {//必须从5开始

这样确实可以遍历每种两个H-numbers的组合，但是直接打出h-prime和H-semi-prime是不够的，因此采用下面的方法。

当我们判断i，j是否同为H-prime时其实是有问题的，比如i=5,j=81时，我们会得到isp[5*81]=1，但是显然81=9*9并不是 H-prime，j从5开始循环解决了这个问题，当i=9，j=9时他会更新isp[81]=-1，然后再i=81时，他会更新所有i*81的isp数组为-1.

		if (isp[i] == 0 && isp[j] == 0)isp[mul] = 1;

#define MAX 1000005memset(isp, 0, sizeof(isp));
memset(a, 0, sizeof(a));
for (ll i = 5; i < MAX; i += 4) {for (ll j = 5; j<MAX; j += 4) {//必须从5开始ll mul = i * j;if (mul >= MAX)break;if (isp[i] == 0 && isp[j] == 0)isp[mul] = 1;elseisp[mul] = -1;}}

#define inf 0x3f3f3f3f
#define ll long long
#define vec vector<int>
#define P pair<int,int>
#define MAX 1000005int a[MAX], isp[MAX];int main() {memset(isp, 0, sizeof(isp));memset(a, 0, sizeof(a));for (ll i = 5; i < MAX; i += 4) {for (ll j = 5; j<MAX; j += 4) {//必须从5开始ll mul = i * j;//肯定是以i为基数的一个值if (mul >= MAX)break;if (isp[i] == 0 && isp[j] == 0)isp[mul] = 1;elseisp[mul] = -1;}}for (int i = 25; i < MAX; i++)if (isp[i] == 1)a[i] = a[i - 1] + 1;else a[i] = a[i - 1];int n;while (cin >> n && n)cout << n << ' ' << a[n] << endl;
}