C语言判断数是否为两素数乘积的代码对大数无效问题排查

我开发了以下C语言代码，包含两个函数：

• modozero：寻找输入数的下一个素数，目前功能正常
• modoum：判断一个数是否为两个素数的乘积，但该函数处理大数时无法正常结束，怀疑问题与执行时间有关，但不确定。

原代码 #

#include <stdio.h>
#include <stdlib.h>

long int modozero(long int num);
long int primeverification(long int num);
long int modoum(long int num);

int main(int argc, char *argv[]) {
    long int modo, num;

    modo = atoi(argv[1]);
    num = atoi(argv[2]);

    if (!modo)
        modozero(num);
    else
        modoum(num);

    return 0;
}

long int primeverification(long int num) {
    long int i, remainder;
    for (i = 2; i <= num / 2; i++) {
        remainder = num % i;
        if (!remainder)
            return 0;
    }
    return 1;
}

long int modozero(long int num) {
    long int isprime = 0;
    while (!isprime) {
        num++;

        isprime = primeverification(num);
        printf("is prime %ld \n", isprime);
    }
    printf("%ld \n", num);
    return num;
}

long int modoum(long int num) {
    long int i, j, remainder;

    for (i = 2; i <= num / 2; i++) {
        if (primeverification(i)) {
            remainder = num % i;

            if (!remainder) {
                j = num / i;
                if (primeverification(j)) {
                    printf("%ld %ld", i, j);
                    return 0;
                }
            }
        }
    }
    return 0;
}

执行示例 #

$ ./prime 1 6
2 3

$ ./prime 1 1000
# 无输出，因为1000不是两素数的乘积

$ ./prime 1 908118221
30133 30137

$ ./prime 1 908118220
# 输入该值时程序无法结束执行
# 奇怪的是这个数比之前测试的数小，且已知不是两素数乘积，却无法正常运行

问题分析 #

程序卡住的核心原因是素数判断函数primeverification和modoum的遍历效率极低：

1. primeverification循环到num/2，实际判断素数只需要检查到sqrt(num)即可——如果一个数有大于其平方根的因数，对应的另一个因数必然小于平方根，无需重复检查。
2. modoum循环到num/2，同理，遍历到sqrt(num)就足够，超过后会重复检查已经验证过的因数对。
3. 对于908118220这类非素数乘积的大数，原代码需要遍历大量数字，且每个数字的素数判断都要执行O(n)的循环，导致总耗时指数级增长，看起来像程序卡住。

优化方案 #

1. 优化素数判断函数 #

减少循环次数，提前排除偶数等非素数情况：

#include <math.h> // 需要添加此头文件

long int primeverification(long int num) {
    if (num <= 1) return 0;
    if (num == 2) return 1;
    if (num % 2 == 0) return 0; // 偶数直接排除（除2外）
    
    long int sqrt_num = sqrt(num);
    // 只遍历奇数，减少一半循环次数
    for (long int i = 3; i <= sqrt_num; i += 2) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

2. 优化modoum函数的遍历上限 #

将循环上限从num/2改为sqrt(num)，避免无效遍历：

long int modoum(long int num) {
    long int sqrt_num = sqrt(num);
    for (long int i = 2; i <= sqrt_num; i++) {
        if (primeverification(i)) {
            if (num % i == 0) {
                long int j = num / i;
                if (primeverification(j)) {
                    printf("%ld %ld\n", i, j);
                    return 0;
                }
            }
        }
    }
    printf("该数不是两个素数的乘积\n"); // 添加友好提示
    return 0;
}

3. 修复整数溢出问题 #

main函数中使用atoi转换大数可能溢出，改为atol：

modo = atol(argv[1]);
num = atol(argv[2]);

优化后效果 #

优化后的代码处理908118220这类大数时，会快速完成遍历和素数判断，不会出现卡住的情况，同时能正确输出结果提示。

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