求解欧拉计划第3题：大整数最大质因数代码错误排查

咱们来一步步拆解你代码里的问题，为什么输出会是1471而不是正确的6857：

核心错误点 #

你的代码有两个关键逻辑漏洞：

1. 错误的x赋值时机：在for循环里，你每次迭代都把x = i，不管i是不是n的质因数。这就导致最后x会停在循环执行的最后一个i，而不是真正的最大质因数。
2. 未处理剩余的质数n：当循环结束后，如果n仍然大于1，说明这个剩下的n本身就是一个质数（因为所有小于等于它平方根的因数都已经被除尽了），而它才是最大的质因数，你的代码完全没处理这种情况。

举个具体的例子：当处理到i=1471时，n会被除以1471，此时n变成了6857。接下来循环继续，i从1473开始递增，但此时sqrt(6857)大约是82.8，i很快就会超过这个值，循环直接结束。这时候你没有把剩下的6857赋值给x，所以x就停在了最后一次赋值的1471。

修正后的代码 #

#include <iostream>
using namespace std;

int main() {
    long long x = 1; // 初始化x为1，避免未定义行为
    long long n = 600851475143; // 目标分解数

    // 处理因数2
    while (n % 2 == 0) {
        n /= 2;
        x = 2; // 只有当2是因数时才更新x
    }

    // 处理因数3
    while (n % 3 == 0) {
        n /= 3;
        x = 3; // 只有当3是因数时才更新x
    }

    // 处理从5开始的所有奇数因数
    for (long long i = 5; i * i <= n; i += 2) {
        // 当i是n的因数时，持续除尽
        while (n % i == 0) {
            n /= i;
            x = i; // 仅在i是质因数时更新x
        }
    }

    // 若剩余n>1，说明它本身是最大的质数
    if (n > 1) {
        x = n;
    }

    cout << x << endl;
    return 0;
}

关键修正说明 #

• 调整x的赋值逻辑：把x = i移到内部的while循环里，只有当i确实是n的质因数时才更新x，确保x只记录真正的质因数。
• 优化循环条件：用i * i <= n代替i <= sqrt(n)，既避免了浮点运算的精度问题，又能自动适配不断变小的n。
• 新增剩余质数判断：循环结束后检查n > 1，如果成立，说明剩下的n就是最大的质因数，直接赋值给x。

运行这段修正后的代码，就能得到正确的结果6857啦。

内容的提问来源于stack exchange，提问作者user13793398