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 位数字时，它 returns 为零。

Answer 1

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


int main() {

long long int result =factors(6051475143);
printf("%lld",result); 
return 0;
}

factors(long long int number)
{
    long int factor[1000000];
    long long int x;
    long int index=0,i=1;
    for(;i<800000; i++)
    {
        if (number%i==0)
        {
            factor[index] = i;
            index+=1;
        
        }
    }
    x = findprime(factor,index);
    return x;
}

int findprime(long int prime[],long int size)
{
    long 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;
}

Answer 2

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

你的程序有 未定义的行为，即使是小数字：result = factors(6051475143) 不能可靠地存储任何有用的东西，因为 factors 被定义为 void 函数，甚至没有 return 语句。它偶然起作用，因为最后一条语句 findprime(factor, 100000); 将 findprime 的 return 值留在寄存器中，其中 main 检索它期望的 int 结果factors()，编译器因缺少原型而推断出的 return 类型。

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

这是修改后的版本：

#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;
}

c中的溢出错误以找到十二位数字的主要因素

Overflow error in c to find prime factors of a twelve-digit number

c

primes

integer-overflow

prime-factoring