题解 | #几乎是质数#

题目链接

题目描述

如果一个正整数恰好拥有两个不同的质因子，则称该数为“几乎是质数”。给定一个正整数 $N$ ，请计算区间 $[1, N]$ 内“几乎是质数”的数量。

解题思路

本题要求我们统计一个区间内满足特定条件的数的个数。这个条件是“恰好拥有两个不同的质因子”。

一个直接的想法是遍历从 1 到 $N$ 的每个数，对每个数进行质因数分解，然后统计其不同质因子的数量。如果数量恰好为 2，则计数器加一。但这种方法的时间复杂度大约是 $O(N\sqrt{N})$ ，对于常见的 $N$ 的范围（如 $10^6$ ）来说，可能会超时。

更高效的方法是使用筛法。我们可以预处理出从 1 到 $N$ 每个数包含多少个不同的质因子。具体步骤如下：

创建一个数组 count，大小为 $N+1$ ，用来记录每个数有多少个不同的质因子。count[i] 表示数字 i 的不同质因子个数。
从 $i = 2$ 开始遍历到 $N$ 。
如果 count[i] 的值仍然为 0，说明在之前的遍历中 i 没有被任何更小的数（作为因子）标记过，因此 $i$ 是一个质数。
既然 $i$ 是一个质数，那么它就是它所有倍数的一个质因子。于是，我们遍历 $i$ 的所有倍数 $j$ （即 $j = i, 2i, 3i, \dots$ ），只要 $j \le N$ ，就将 count[j] 的值加 1。
遍历完成后，count 数组就记录了 1 到 $N$ 每个数所含不同质因子的个数。
最后，我们再遍历一次 count 数组，统计其中值为 2 的元素个数，即为最终答案。

这个算法类似于埃氏筛法（Sieve of Eratosthenes），其时间复杂度远优于暴力分解。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> count(n + 1, 0); // 记录每个数不同质因子的个数

    // 类似筛法的过程
    for (int i = 2; i <= n; ++i) {
        // 如果 count[i] == 0，说明 i 是质数
        if (count[i] == 0) {
            // 为 i 的所有倍数增加一个质因子 i
            for (int j = i; j <= n; j += i) {
                count[j]++;
            }
        }
    }

    int ans = 0;
    // 统计不同质因子个数为 2 的数的数量
    for (int i = 1; i <= n; ++i) {
        if (count[i] == 2) {
            ans++;
        }
    }

    cout << ans << "\n";
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] count = new int[n + 1]; // 记录每个数不同质因子的个数

        // 类似筛法的过程
        for (int i = 2; i <= n; i++) {
            // 如果 count[i] == 0，说明 i 是质数
            if (count[i] == 0) {
                // 为 i 的所有倍数增加一个质因子 i
                for (int j = i; j <= n; j += i) {
                    count[j]++;
                }
            }
        }

        int ans = 0;
        // 统计不同质因子个数为 2 的数的数量
        for (int i = 1; i <= n; i++) {
            if (count[i] == 2) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}

n = int(input())

# 记录每个数不同质因子的个数
count = [0] * (n + 1)

# 类似筛法的过程
for i in range(2, n + 1):
    # 如果 count[i] == 0，说明 i 是质数
    if count[i] == 0:
        # 为 i 的所有倍数增加一个质因子 i
        for j in range(i, n + 1, i):
            count[j] += 1

ans = 0
# 统计不同质因子个数为 2 的数的数量
for i in range(1, n + 1):
    if count[i] == 2:
        ans += 1

print(ans)

算法及复杂度

算法：筛法
时间复杂度： $O(N \log \log N)$ 。外层循环遍历到 $N$ ，内层循环的次数总和为 $N/2 + N/3 + N/5 + \dots$ （质数的倒数和），这是一个调和级数的变种，其总和近似为 $N \log \log N$ 。
空间复杂度： $O(N)$ ，需要一个大小为 $N+1$ 的数组来存储每个数不同质因子的个数。