齐全的题解 | 质数ABC

#include <bits/stdc++.h>
using namespace std;

/*
 * @brief 判断一个数是否为质数 (Prime Check)
 * @param m 需要被判断的整数
 * @return 如果 m 是质数，返回 true，否则返回 false
 */
bool ip(long long m) {
    if (m < 2) return 0;
    if (m == 2) return 1;
    if (m % 2 == 0) return 0;
    for (long long i = 3; i * i <= m; i += 2)
        if (m % i == 0) return 0;
    return 1;
}

/*
 * @brief 找到大于或等于 s 的最小质数 (Next Prime)
 * @param s 起始搜索整数
 * @return 大于或等于 s 的最小质数
 */
long long np(long long s) {
    if (s <= 2) return 2;
    if (s % 2 == 0) s++;
    while (1) {
        if (ip(s)) return s;
        s += 2;
    }
}

int main() {
    // 使用 long long 以支持 up to 10^12 的输入
    long long n;
    cin >> n;

    // cnt 用于记录满足条件的 (a, b, c) 三元组的数量
    int cnt = 0;

    // 从最小的质数 '2' 开始迭代 'a'
    long long a = 2;
    while (1) {
        long long a2 = a * a;

        // 找到大于 'a' 的最小质数作为 'b' 的起始值
        long long b = np(a + 1);

        // 找到大于 'b' 的最小质数作为 'c' 的起始值
        long long cm = np(b + 1);

        // 【重要的剪枝优化】
        // 检查当前的 a² 是否已经太大。
        // 如果 a² > n/(b*cm²)，那么即使取最小的 b 和 c，a²*b*c² 也会超过 n。
        // 此时，当前的 'a' 以及更大的 'a' 都不可能找到合法的 (b,c) 对。
        // 所以可以直接 break 掉最外层的 a 循环，程序结束。
        if (a2 > n / (b * cm * cm)) {
            break;
        }

        // 内层循环，迭代 'b'
        while (1) {
            // 计算 a² * b 的值，这是一个固定部分
            long long p = a2 * b;

            // 为了满足 p * c² <= n，我们可以推导出 c 的最大值：
            // c² <= n / p
            // c <= sqrt(n / p)
            // 所以 c 的上限是 sqrt(n / p)
            long long mc = sqrt(n / p);
            
            // 如果 c 的理论最大值 mc 小于等于 'b'，
            // 那么不可能找到一个大于 'b' 的质数 'c' 来满足条件。
            // 此时，当前的 'b' 已经太大，需要尝试下一个更大的 'a'。
            // 所以 break 掉当前的 b 循环。
            if (mc <= b) {
                break;
            }

            // 找到大于 'b' 的最小质数作为当前 'b' 对应的 'c' 的起始值
            long long c = np(b + 1);

            // 遍历所有大于 'b' 且小于等于 mc 的质数 'c'
            while (c <= mc) {
                // 每找到一个符合条件的 'c'，就意味着找到了一组 (a,b,c)
                cnt++;
                // 寻找下一个质数作为 'c'
                c = np(c + 1);
            }

            // 当前 'b' 已经遍历完所有可能的 'c'，寻找下一个更大的质数作为 'b'
            b = np(b + 1);
        }

        // 当前 'a' 已经遍历完所有可能的 'b'，寻找下一个更大的质数作为 'a'
        a = np(a + 1);
    }

    // 输出最终的计数结果
    cout << cnt;
    return 0;
}

总结代码的核心逻辑：

本代码采用了三层嵌套循环的结构来遍历所有可能的质数三元组 (a, b, c)，并通过数学推导来优化循环的上限，避免了不必要的计算。

1. 外层循环 (a)：从最小的质数 2 开始，依次尝试每个质数作为 a。
2. 中层循环 (b)：对于每个 a，从比 a 大的下一个质数开始，依次尝试每个质数作为 b。
3. 内层循环 (c)：对于每一对 (a, b)，计算出 c 的最大可能值 mc = sqrt(n / (a*a*b))。然后从比 b 大的下一个质数开始，依次尝试每个质数作为 c，直到 c 超过 mc。每找到一个符合条件的 c，计数器 cnt 就加一。
4. 剪枝优化：
   • 在 b 循环内部，如果计算出的 mc 小于等于当前的 b，说明没有比 b 大的 c 能满足条件，此时 b 已经太大，需要 break b 循环，让 a 增加。
   • 在 a 循环的开头，会做一个预判。如果当前 a 的平方，即使乘以最小的可能 b 和 c 的平方，结果也已经超过 n，那么说明当前 a 以及所有更大的 a 都不可能找到符合条件的 (b, c) 对，可以直接 break a 循环，程序结束。

这个算法的效率在很大程度上依赖于 next_prime 和 is_prime 函数的效率。对于 n 达到 10^12 的情况，这个算法是可行的，但如果 n 再大很多，可能就需要更高级的质数筛选方法（如埃拉托斯特尼筛法的变体）来预先处理质数，以提高效率。

无注释版：

#include <bits/stdc++.h>
using namespace std;
bool ip(long long m) {
    if (m < 2) return 0;
    if (m == 2) return 1;
    if (m % 2 == 0) return 0;
    for (long long i = 3; i * i <= m; i += 2)
        if (m % i == 0) return 0;
    return 1;
}
long long np(long long s) {
    if (s <= 2) return 2;
    if (s % 2 == 0) s++;
    while (1) {
        if (ip(s)) return s;
        s += 2;
    }
}
int main() {
    long long n;
    cin >> n;
    int cnt = 0;
    long long a = 2;
    while (1) {
        long long a2 = a * a;
        long long b = np(a + 1);
        long long cm = np(b + 1);
        if (a2 > n / (b * cm * cm)) {
            break;
        }
        while (1) {
            long long p = a2 * b;
            long long mc = sqrt(n / p);
            
            if (mc <= b) {
                break;
            }
            long long c = np(b + 1);
            while (c <= mc) {
                cnt++;
                c = np(c + 1);
            }
            b = np(b + 1);
        }
        a = np(a + 1);
    }
    cout << cnt;
    return 0;
}