c - c 中查找 12 位数字的质因数时出现溢出错误

Question

我想解决这个问题:https://projecteuler.net/problem=3通过这个程序，但我不确定它使用 long long int 的真正方法。

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

int main(int argc, char *argv[]) {
    long long int result = factors(6051475143);
    printf("%lld", result); 
    return 0;
}

void factors(int number) {
    int factor[100000];
    int index = 0, i = 1;
    for (; i < number; i++) {
        if (number % i == 0) {
            factor[index] = i;
            index += 1;
        }
    }
    findprime(factor, 100000);
}

int findprime(int prime[], int size) {
    int i = 0, j;
    long long int latestprime;
    for(; i < size; i++) {
        if (prime[i] == 0)
            break;
        int is_prime = 1;
        for (j = 2; j < prime[i]; j++) {
            if (prime[i] % j == 0 && prime[i] != j) {   
                is_prime = 0;
                break;
            }
        }
        if (is_prime == 1)
            latestprime = prime[i];
    } 
    return latestprime;
}

如果我尝试 10 位数字，它会起作用，但当我尝试 12 位数字时，它会返回零。

Answer 1

要解决这个问题，您确实需要一个足够大的类型来表示数字。 unsigned long long 被指定为至少有 64 个值位，即 18446744073709551615。

您的程序有未定义的行为，即使是少量:result = Factors(6051475143) 不能可靠地存储任何有用的信息，因为 factors 是定义为 void 函数，甚至没有 return 语句。它的工作是偶然的，因为最后一个语句 findprime(factor, 100000); 将 findprime 的返回值留在寄存器中，其中 main 检索什么它期望是 factors() 的 int 结果，这是编译器因缺乏原型(prototype)而推断出的返回类型。

要找到最大的质因数，您应该尝试因数，并在找到能整除它的数时减少该数。

这是修改后的版本:

#include <stdio.h>

unsigned long long largest_factor(unsigned long long number) {
    unsigned long long p;
    if (number < 2)
        return number;
    for (p = 2; p * p <= number; p++) {
        while (number % p == 0) {
            number /= p;
        }
    }
    if (number == 1)
        return p;
    else
        return number;
}

int main(int argc, char *argv[]) {
    printf("%llu\n", largest_factor(6051475143)); 
    return 0;
}