卡迈克尔数是满足Korselt准则的合数：无平方因子，且对每个素因子p都有(p−1)∣(n−1)；需先排除素数、偶数及n
什么是卡迈克尔数？先看判定条件
卡迈克尔数不是素数，但满足费马小定理的“伪素性”：对所有与它互质的整数 a，都有 a^n ≡ a (mod n)。等价地，n 是合数，且对每个它的素因子 p，都有 (p − 1) | (n − 1)，同时 n 是无平方因子的（即不被任何素数的平方整除）。
这意味着判断不能只靠试除法测素性，必须验证三个条件：
-
n > 2且为合数（非素数、非 1） -
n是 square-free：分解后每个素因子指数均为 1 - 对每个素因子
p，(n - 1) % (p - 1) == 0
如何高效分解 n 并检查 square-free 性
暴力试除到 sqrt(n) 即可，不需要筛表或 Pollard-Rho。关键点在于：一旦发现某个素因子 p 满足 p*p 整除 n，立刻返回 false（违反 square-free）。
bool is_square_free(long long n) {
if (n <p>注意：</p>
- 循环中要实时更新
n，否则会漏判残留大素因子 - 最后剩余的
n > 1是一个素因子（且只出现一次），不用再验平方 - 用
long long防止p*p溢出，尤其当n接近INT_MAX时
完整判定函数怎么写（含素性判断和因子遍历）
不能复用 is_prime 判定合数 —— 因为卡迈克尔数必须是合数，所以先排除素数；但更高效的做法是在分解过程中同步收集素因子，并顺便确认是否为合数（即至少找到一个因子）。
bool is_carmichael(long long n) {
if (n vector<long long> factors;
long long temp = n;
for (long long p = 2; p * p 1) factors.push_back(temp);
if (factors.size() <p>}</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>容易踩的坑：</p>
<ul>
<li>忘记检查 <code>n</code> 是否为素数：若 <code>n</code> 是素数，即使满足 <code>(n−1)%(p−1)</code>（此时只有自身一个因子），也不算卡迈克尔数</li>
<li>误把 <code>1</code> 或 <code>4</code> 当作候选：它们不满足合数前提，直接排除</li>
<li>没处理 <code>n</code> 分解后剩余的大素因子（即 <code>temp > 1</code> 的情况），导致漏因子、条件验证不全</li>
</ul>
<h3>实际使用时要注意数值范围和性能边界</h3>
<p>卡迈克尔数很稀疏：前 10^6 内只有 43 个。所以对单次查询，O(√n) 分解完全可行；但若批量判断 10^5 个数，就该预筛小素数或缓存已知卡迈克尔数（如 561, 1105, 1729, 2465…）。</p>
<p>另外：</p>
<ul>
<li>
<code>int</code> 类型只能安全处理到约 46340²，建议统一用 <code>long long</code>
</li>
<li>标准库没有现成的 <code>is_carmichael</code>，别试图用 <code>std::pow</code> + 模运算模拟费马测试——那会溢出且慢，还无法 100% 判定（仅概率性）</li>
<li>某些实现错误地认为“对几个 <code>a</code> 满足 <code>a^n % n == a</code> 就是卡迈克尔数”，这是错的：必须对所有与 <code>n</code> 互质的 <code>a</code> 成立，而等价判定正是上面三条数论条件</li>
</ul>
<p>真正要命的是漏掉 square-free 检查 —— 比如 1105 = 5 × 13 × 17，满足所有条件；但若误把 45 = 3² × 5 当作候选，虽然 <code>(45−1)%(3−1)==0</code> 且 <code>(45−1)%(5−1)==0</code>，却因含平方因子被排除。这个细节几乎所有人第一次写都会错。</p></long>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
