合数是大于1且非质数的正整数，必有真因子；1既非质数也非合数，2是质数，4是最小合数；判断需先验证n>1，再试除2到√n。

什么是合数？先明确判断边界

合数是大于 1 的正整数，且不是质数——也就是说，它至少有一个真因子（即除 1 和自身外的正因数）。注意：1 既不是质数也不是合数；2 是质数，不是合数；4 是最小的合数。

所以判断逻辑起点必须是：n > 1，否则直接返回 false（不是合数）。

基础试除法：O(√n) 时间内完成判断

最常用、最直观的方法是遍历 2 到 sqrt(n)，看是否有能整除 n 的数。只要找到一个，就是合数。

bool isComposite(int n) {
    if (n <= 1) return false;
    if (n == 2) return false;  // 2 是质数
    if (n % 2 == 0) return true;  // 偶数（除 2 外）都是合数
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return true;
    }
    return false;
}

• i * i 比 i 更安全，避免浮点误差和类型转换开销
• 先特判 2，再跳过所有偶数，减少一半循环次数
• 注意：int 类型下，i * i 可能溢出（如 n 接近 INT_MAX），此时应改用 long long i 或改用 i

小范围预处理：用埃氏筛批量标记合数

如果需要频繁判断多个数（比如在 [2, 10^6] 内查几千次），预先筛出合数比反复试除快得多。

立即学习“C++免费学习笔记（深入）”；

const int MAXN = 1000001;
bool is_composite[MAXN] = {false};
void sieve() {
is_composite[0] = is_composite[1] = true;  // 0 和 1 不是合数，但按定义常设为 true 方便统一处理？
// 实际上我们只关心 ≥2：让 is_composite[i] 表示 i 是否为合数（i≥2）
for (int i = 2; i  i < MAXN; ++i) {
if (!is_composite[i]) {  // i 是质数
for (int j = i  i; j < MAXN; j += i) {
is_composite[j] = true;  // 标记合数
}
}
}
}

• is_composite[i] 对 i ≥ 2 为 true ⇔ i 是合数
• 筛完后，单次查询是 O(1)
• 注意：数组大小要覆盖到最大待查数，且初始化时 is_composite[0] 和 is_composite[1] 应设为 false（它们不是合数），除非你约定只查 ≥2

容易踩的坑：负数、0、大整数、类型隐式转换

• isComposite(-5) 或 isComposite(0) 必须返回 false，合数定义仅针对正整数 ≥2
• 使用 unsigned int 时，n % 2 == 0 对 n=0 会误判（0 不是合数），所以开头仍需 n 拦截
• 若输入可能是 long long，循环变量也得用 long long，否则 i * i 溢出导致死循环或越界
• C++ 中 sqrt(n) 返回 double，对大整数可能精度丢失，例如 sqrt(999999999999999999) 可能向下取整错误，坚决避免

实际写的时候，别图省事写 sqrt(n)，老实用 i 或 i * i （并确保类型不溢出）。

https://www.php.cn/faq/1987027.html