c - 比 int 更大的数的质因数分解

Question

该程序对 C 语言中的数进行质因数分解。

#include <stdio.h>

int main(void) {
    int number, i, p, n, factors, count;
    int numbers[1000000];
    int counter = 0;
    char text[100000]; 

    for (count = 0; count < 1000000; count++) {
        fgets(text, 10000000, stdin);
        if (sscanf(text, "%d", &number) == 1) {
            if (number == 0)
                break;
            numbers[count] = number;
        } else {
            numbers[count] = 0;
        }
    }
    counter = 0; 
    for (i = 0; i < count; i++) {
        if ((numbers[i] < 0) || (numbers[i] == 0)) {
            fprintf(stderr, "Error: Wrong Input!\n");
            return 100;
            break;
        }
        number = numbers[i];
        printf("Prime factorization of nubmer %d is:\n", number);
        factors = 0;
        for (p = 2; p * p <= number; p += 1 + (p & 1)) {
            if (number % p == 0) {
                n = 0;
                factors++;
                do {
                    number /= p;
                    n++;
                } while (number % p == 0);
                if (n == 1) {
                    printf("%d ", p);
                    ++counter;
                } else 
                    printf("%d^%d ", p, n);
                ++counter;

                if (count > 0 && number != 1) 
                    printf("x ");
            }
        }
        if (factors == 0 || number != 1)
            printf("%d", number);
        printf("\n");
    }
    return 0;
}

此程序适用于小于 10⁸ 的数字。但我的问题是，是否有一种方法可以让这个程序即使对于像 10¹² 这样的数字。我知道 int 还不够，但是当我尝试使用 long int 时，它不起作用。我还听说过一些关于 malloc 的事情，但我一直未能实现(理解)它。

Answer 1

对大数进行因式分解通常需要比简单的试除法更微妙的方法。这是一种可能的概述方法:

1. 列出所有素数，例如 25,000。
2. 使用该列表删除 25,000 以下的所有质因数。
3. 如果余数 > 1，则使用 Miller-Rabin 测试或类似方法检查余数是否为素数。
4. 如果余数是质数，那么您就找到了最后一个因子。
5. 如果余数不是素数，那么您就必须将其因式分解。恐怕这将不可避免地很慢。