在c中查找十二位数的素数的溢出错误

Question

我想解决这个问题：https://projecteuler.net/problem=3通过这个程序，但我不确定它使用长整型的真实方式

#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结果，这是编译器从缺少原型中推断出的返回类型。

要找到最大的素因子，你应该尝试因子，只要你找到一个将其平均的因子，就应该减少这个数。

这是一个修改版本：

#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("%llun", largest_factor(6051475143)); 
return 0;
}

Answer 2

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