C++如何判断一个正整数是否为合数的阶乘（Factorial-判定）-C++-PHP中文网

“合数的阶乘”指合数n的阶乘n!，即判断给定正整数x是否等于某个合数n（n≥4）的阶乘；因阶乘增长极快，只需预计算n=4至20的合数阶乘并查表，溢出前终止。

c++如何判断一个正整数是否为合数的阶乘（factorial-判定）

什么是“合数的阶乘”？先厘清概念再写代码

“一个正整数是否为合数的阶乘”这个说法本身有歧义——阶乘 n! 是运算结果，而“合数的阶乘”不是标准数学定义。实际想问的通常是：给定正整数 x，是否存在某个合数 n（即 n > 1 且 n 不是质数），使得 x == n!？

注意：这不是判断 x 是否为“合数”，也不是判断 x 是否“能被某个阶乘整除”。核心是反向查找：枚举合数 n，算出 n!，看是否等于输入值。

由于阶乘增长极快，12! = 479001600 已超 int 范围，20! 约为 2.43e18，超出 unsigned long long（约 1.84e19）的临界点也很快。所以实际可行范围非常有限——最多检查到 n = 20 左右。

如何预生成合数阶乘表并查表？最稳的解法

与其每次运行时动态计算、反复判断质数，不如提前把所有「合数 n 对应的 n!」存进一个集合（如 std::unordered_set<unsigned long></unsigned>）。输入 x 时直接查表，O(1) 完事。

关键点：

合数从 4 开始（1 非质非合，2、3 是质数，4 是最小合数）
计算 n! 时用 unsigned long long，但必须在溢出前停止——一旦乘法结果 （回绕）或超过预设上限（如 <code>ULLONG_MAX / n），就终止
只存 n 为合数时的 n!，跳过 n = 2, 3, 5, 7, 11, 13, 17, 19...

示例片段（含防溢出）：

std::unordered_set<unsigned long> factorial_of_composites;
unsigned long long fact = 1;
for (int n = 2; n  ULLONG_MAX / n) break; // 溢出防护
        fact *= n;
        factorial_of_composites.insert(fact);
    }
}
</unsigned>

更严谨的合数判断可用简单试除（n 时完全够用），不必上筛法。