C语言质因数求解函数仅对2有效，高质数无法识别问题排查

问题根源 #

根据你的描述，函数能正确分解8但抓不住24里的3，大概率是这几个逻辑漏洞导致的：

• 没把当前质因数除尽就换数：找到能整除n的质数后，只做一次除法就跳到下一个质数。比如24拆成12后，还能继续用2拆，但代码直接去查3，最后剩下的3又没处理，就漏掉了。
• 循环上限用了原始输入值：比如用sqrt(24)作为遍历上限，当n缩小到3时，3的平方根是1.7，循环直接终止，没机会检查3。
• 没处理最后剩下的质数：当分解到最后n是个大于1的质数时，没把它加到链表就结束了。

修复方案&代码示例 #

假设你的原有代码是类似下面的错误版本（用预设质数列表的情况）：

Node* primefactors(int num) {
    Node* list = create_list();
    add_to_tail(list, 1);
    int n = num;
    int primes[] = {2,3,5,7,11};
    int count = sizeof(primes)/sizeof(primes[0]);
    
    for (int i=0; i<count; i++) {
        if (n % primes[i] == 0) {
            add_to_tail(list, primes[i]);
            n /= primes[i];
            // 错在这：只除一次就换下一个质数，没除尽当前因子
        }
    }
    // 错在这：没处理最后剩下的质数
    return list;
}

修复后的通用版本（无需预设质数列表） #

这个版本效率更高，不用提前定义质数：

Node* primefactors(int num) {
    Node* list = create_list();
    add_to_tail(list, 1);
    int n = num;

    // 先把2的因子全部除尽
    while (n % 2 == 0) {
        add_to_tail(list, 2);
        n /= 2;
    }

    // 处理所有奇数因子，从3开始每次加2（跳过偶数）
    for (int i=3; i*i <=n; i+=2) {
        // 循环除尽当前奇数的所有因子
        while (n % i ==0) {
            add_to_tail(list, i);
            n /=i;
        }
    }

    // 如果最后剩下的n大于2，说明它本身是质数
    if (n>2) {
        add_to_tail(list, n);
    }

    return list;
}

如果你必须用预设质数列表的修复版本 #

Node* primefactors(int num) {
    Node* list = create_list();
    add_to_tail(list, 1);
    int n = num;
    int primes[] = {2,3,5,7,11,13,17};
    int count = sizeof(primes)/sizeof(primes[0]);
    int i=0;

    while (i<count && primes[i]*primes[i] <=n) {
        // 循环除尽当前质数的所有因子
        while (n%primes[i]==0) {
            add_to_tail(list, primes[i]);
            n /= primes[i];
        }
        i++;
    }

    // 处理剩余的质数
    if (n>1) {
        add_to_tail(list, n);
    }

    return list;
}

验证效果 #

• 调用primefactors(8)：2会被除三次，n最终变成1，链表输出1,2,2,2，符合预期。
• 调用primefactors(24)：先除三次2得到n=3，然后循环检查3，把3加入链表，最终输出1,2,2,2,3，正确分解所有质因数。

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