一、详细思路分析

1. 问题重述与定义明确

我们需要找出区间 [S, E] 内的半质数个数。

• 质数：只能被 1 和自身整除的大于 1 的自然数。
• 半质数：恰好等于两个质数的乘积（这两个质数可以相同，如 $4=2\times2$；也可以不同，如 $6=2\times3$）。

2. 核心算法选择：筛法思想

原代码的问题在于最后使用了双重循环枚举质数对，当数据范围达到 $5 \times 10^6$ 时，质数数量约为 34 万，双重循环的时间复杂度为 $O(\pi(n)^2)$（$\pi(n)$ 为小于 $n$ 的质数个数），这会导致严重超时。

因此，我们采用逆向筛法的思路：

1. 第一步：埃氏筛预处理：先筛出所有质数，并标记每个数是否为质数。
2. 第二步：标记半质数：利用筛法思想，枚举每个质数 $p$，再枚举另一个质数 $q$（要求 $q \ge p$，避免重复计数，如 $2 \times 3$ 和 $3 \times 2$ 只算一次），将乘积 $p \times q$ 标记为半质数。
3. 第三步：统计结果：遍历区间 $[S, E]$，统计被标记为半质数的数的个数。

3. 复杂度与空间分析

• 时间复杂度：埃氏筛为 $O(n \log \log n)$，标记半质数的过程也接近 $O(n \log \log n)$，对于 $n=5 \times 10^6$ 完全可以通过。
• 空间复杂度：根据题目范围 $E < 5000000$，我们只需开 $5 \times 10^6 + 10$ 大小的数组，节省内存。

二、代码实现（含详细注释）

三、代码关键点解释

1. q >= p 的意义：在标记半质数时，我们强制第二个质数 $q$ 大于等于第一个质数 $p$。这是为了避免重复计数。例如，$6=2 \times 3$ 和 $6=3 \times 2$ 是同一个半质数，我们只希望标记一次。