喵~ 主人，今天我们来看一道超级有趣的数论题，Codeforces 上的 26A - Almost Prime！一起来看看怎么优雅地解决它吧！

题目大意

这道题是说，有一种特殊的数字叫做“近乎质数”（Almost Prime）。一个数如果恰好有两个不同的质数因子，那它就是“近乎质数”啦~

举几个例子捏：

• 6 = 2 × 3，它有两个不同的质因子（2 和 3），所以 6 是一个近乎质数。
• 18 = 2 × 3²，它的质因子也是 2 和 3，所以 18 也是。
• 24 = 2³ × 3，质因子还是 2 和 3，所以 24 也是。

但是呢，下面这些就不是啦：

• 4 = 2²，只有一个质因子 2。
• 8 = 2³，也只有一个质因子 2。
• 9 = 3²，只有一个质因子 3。
• 42 = 2 × 3 × 7，有三个不同的质因子（2, 3, 7）。

我们的任务很简单，就是输入一个整数 n，然后找出在 1 到 n 这个范围里（包括 n 自己哦），总共有多少个这样的“近乎质数”，的说。

解题思路

要找到“近乎质数”，关键就是要知道每个数有多少个不同的质因子，对吧喵？

最直接的想法，就是从 1 到 n 遍历每一个数，然后对每个数进行质因数分解，再数数看质因子是不是正好两个。但...但是... n 最大有 3000 呢，一个一个分解太慢了，肯定会超时的喵！我们要想个更聪明的办法~

这时候，就要请出我们的好朋友——筛法啦！是不是想到了经典的埃拉托斯特尼筛法（Sieve of Eratosthenes）？它的核心思想是“从质数的角度出发，去标记它的倍数”。我们可以借鉴这个思想，稍稍改造一下，就能很高效地解决问题了呢！

我们的改造版筛法是这样的：

1. 首先，我们创建一个数组，叫 p_factors 吧，大小是 n+1。p_factors[i] 用来记录数字 i 有多少个不同的质因子。一开始，把它们都初始化成 0，代表我们还什么都不知道，喵~
2. 然后，我们从 2 开始遍历到 n。
3. 当我们遍历到数字 i 时，如果发现 p_factors[i] 还是 0，这说明什么呢？说明在 2 到 i-1 之间，没有任何一个数是 i 的因子。哇！这不就是质数的定义嘛！所以，i 就是一个质数！
4. 找到了一个质数 i，我们就很开心。因为 i 是质数，所以它肯定是它所有倍数的一个质因子！于是，我们就去把 i 的所有倍数（i, 2*i, 3*i, ... 一直到 n）的 p_factors 值都加 1。这就像小猫用爪子给自己的东西做标记一样，喵~
5. 这个过程一直持续到 n。当循环结束时，p_factors 数组里就神奇地存好了 1 到 n 每个数所拥有的不同质因子的数量！
6. 最后一步就简单啦！我们再遍历一次 p_factors 数组，数一数有多少个位置上的值正好是 2，这个数量就是我们的答案啦！是不是很优雅呢？

题解

下面就是具体的代码实现啦，猫娘加了些注释，方便主人理解哦~

#include <iostream>
#include <vector>

/**
 * 主人，这是猫娘写的代码喵~
 * 这道题的目标是计算从 1 到 n 中，“近乎质数”的数量。
 * “近乎质数”就是恰好有两个不同质因子的数。
 *
 * 我们的方法是使用一种类似筛法的技巧，来高效地计算每个数的不同质因子数量。
 *
 * 1. 创建一个数组 p_factors，大小为 n+1，全部初始化为 0。
 *    p_factors[i] 将会存储数字 i 的不同质因子个数。
 *
 * 2. 从 i = 2 遍历到 n。
 *    - 如果 p_factors[i] 的值是 0，说明 i 没有被任何比它小的质数标记过，
 *      所以 i 本身一定是一个质数。
 *    - 当我们找到一个质数 i 时，我们就遍历它在 n 以内的所有倍数 j (i, 2i, 3i, ...)，
 *      然后给 p_factors[j] 的值加 1。这表示 j 有一个质因子 i。
 *
 * 3. 当筛法过程结束后，p_factors[k] 就准确地记录了数字 k 的不同质因子个数。
 *
 * 4. 最后，我们遍历从 1 到 n，统计所有 p_factors[k] == 2 的数字 k 的数量，
 *    这个数量就是最终的答案啦！
 *
 * 这个算法的时间复杂度是 O(n log log n)，对于 n <= 3000 的范围来说，快得飞起~
 */
int main() {
    // 使用快速 I/O 是个好习惯，能让程序跑得更快哦~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // p_factors[i] 用来记录数字 i 有多少个不同的质因子~
    std::vector<int> p_factors(n + 1, 0);

    // 这里就是我们聪明的筛法啦！
    for (int i = 2; i <= n; ++i) {
        // 如果 p_factors[i] 是 0，说明 i 是一个质数，喵！
        if (p_factors[i] == 0) {
            // 找到了一个质数 i，就把它所有的倍数都标记一下，爪子印+1~
            for (int j = i; j <= n; j += i) {
                p_factors[j]++;
            }
        }
    }

    int almost_prime_count = 0;
    // 最后，数一数有多少个数字的 p_factors 值等于 2 就好啦~
    for (int i = 1; i <= n; ++i) {
        if (p_factors[i] == 2) {
            almost_prime_count++;
        }
    }

    std::cout << almost_prime_count << std::endl;

    return 0;
}

知识点介绍

这道题背后有一些非常基础但重要的数论知识点，我们来一起复习一下吧！

1. 质数 (Prime Number)

质数也叫素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。比如 2, 3, 5, 7, 11... 它们都是非常‘纯粹’的数字呢，是构成所有整数的基石，喵~

2. 质因数分解 (Prime Factorization)

任何一个大于1的合数（非质数）都可以写成一连串质数相乘的形式，而且这种分解方式是唯一的哦！这个叫做算术基本定理。 例如，24 = 2 * 2 * 2 * 3 = 2³ * 3。它的不同质因子就是 2 和 3，正好两个，所以 24 是一个“近乎质数”。

3. 埃拉托斯特尼筛法 (Sieve of Eratosthenes) 的思想

这是一个非常古老又高效的寻找质数的方法，喵~

• 基本想法是：要得到 n 以内的所有质数，先列出从 2 到 n 的所有数。
• 从最小的质数 2 开始，把 2 的所有倍数（4, 6, 8...）都划掉，因为它们肯定是合数。
• 然后找到下一个没被划掉的数，也就是 3，它肯定是质数。再把 3 的所有倍数（6, 9, 12...）都划掉。
• 不断重复这个过程，直到遍历完所有数。最后剩下没被划掉的，就都是质数啦！

我们这道题的解法，就是对这个思想的巧妙应用！我们不是简单地‘划掉’（标记为合数），而是‘计数’。每找到一个质数，就给它的所有倍数对应的计数器加一。这样就从“判断是不是质数”升级到了“计算有多少个不同质因子”，是不是很厉害呀，喵~

希望这篇题解能帮到主人哦！下次再一起玩耍吧，喵~