C++如何判断一个整数是否为半素数-C++-PHP中文网

半素数是恰好有两个素因子（计重）的正整数，即Ω(n)=2；判断不能依赖因数个数，而需分解并统计素因子重数之和是否为2。

c++如何判断一个整数是否为半素数

半素数（semiprime）是指恰好能分解为两个素数乘积的正整数（这两个素数可以相同，比如 4 = 2 × 2）。注意：1 不是半素数，质数本身（如 5）也不是——它只有一个素因子，而半素数必须有且仅有两个素因子（计重），即 Ω(n) = 2（其中 Ω 是素因子计重函数）。

常见误区是用「因数个数是否等于 3 或 4」来判断，这不可靠：比如 8 = 2³ 有 4 个正因数（1,2,4,8），但它不是半素数；又如 6 = 2×3 有 4 个因数，却是半素数。关键不在因数个数，而在素因子的**重数和数量**。

对给定正整数 n，遍历从 2 到 sqrt(n) 的所有整数 i，尝试整除，并在每次成功整除时检查 i 是否为素数（实际只需检查 i 是否为最小素因子即可，下文说明）。核心逻辑是：把 n 完全分解，记录每个素因子的出现次数，最后判断总重数是否恰好为 2。

先特判 n ：直接返回 <code>false（最小半素数是 4）
用变量 count = 0 累计素因子重数
对每个 i 从 2 循环到 sqrt(n)（含），若 n % i == 0，则：
- 用内层循环不断除以 i，每除一次 count++
- 若除完后 count > 2，可提前返回 false
- 同时确保 i 是素数——但这里无需单独调用 is_prime()：因为 i 是当前最小未被筛掉的因子，只要它能整除 n，它必为素数（否则其素因子早已在更小的 j 时被处理过了）
循环结束后，若 n > 1，说明剩余的 n 本身是一个未被除尽的大素因子，此时 count++
最终返回 count == 2

示例：n = 15 → i=3 整除，15/3=5，count=1；再除不尽；循环结束，剩余 n=5>1，count=2 → true。n = 12 → i=2 整除，12→6→3，count=2；剩余 n=3>1，count=3 → false。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

该方法时间复杂度约为 O(√n)，对 10⁹ 内的数足够快，但仍有几处易错：

下面是一个不依赖额外 is_prime 函数、兼顾正确性与可读性的版本：

bool isSemiprime(int n) {
    if (n  2) return false;
            n /= i;
        }
    }
    if (n > 1) count++;
    return count == 2;
}

这个函数能正确处理 4（2×2）、6（2×3）、9（3×3）、15、21、25 等，也拒绝 1、2、3、8、12、16、17 等非半素数。唯一隐含假设是输入为正整数；若需支持负数或 0，应先加校验。

真正容易被忽略的是：循环中 i 从 2 开始，但没跳过偶数之后的合数——这没关系，因为合数不可能整除当前的 n（它的素因子已被提前除尽），所以不会影响 count 的准确性，只是多做了几次取余判断而已。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！