c - c中的溢出错误以找到十二位数的素数

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检索它所期望的 int factors() 的结果，编译器根据缺少原型(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;
}