提问人：SKCPA- 提问时间：5/29/2015 最后编辑：KartikeySKCPA- 更新时间：9/19/2021 访问量：2060
如何在 C 中找到 600851475143 的最大质因数？[复制]
How to find the largest prime factor of 600851475143 in C? [duplicate]
问：
我尝试使用如下所示的代码找到最大的质因数。
但是，此代码不会返回任何输出，甚至不会返回错误或警告。600851475143
我哪里出错了？
法典：
#include <stdio.h>
int main()
{
int i, j, k, mpf;
for (i = 1; i < 600851475143; i++)
{
if (600851475143 % i == 0)
{
k = 0;
for (j = 1; j <= i; j++)
if (i % j == 0)
k++;
if (k == 2)
mpf = i;
}
}
printf("\nThe largest prime factor of 600851475143 is: %ld\n", mpf);
return 0;
}
答：
0赞
200_success
5/29/2015
#1
循环多达 6000 亿个将需要很长时间——不仅需要很长时间，而且是不可能的，因为它超出了 a 中可以存储的内容（现在通常高达 2^31-1，但根据 C 标准可能小到 2^15-1）。int
您需要的是一种更智能的算法。我建议你不要逐字逐句地给你解决方案，而是看看现有的答案，然后自己用 C 语言制定一个解决方案。
0赞
aakansha
5/29/2015
#2
不应从 1 循环到 600851475143，而应从 2 循环到 600851475143 的平方根：
long long num=600851475143;
long i=2;
while(i<=sqrt(num))
{
//printf("%lu\n",num);
if(num%i==0)
{
while(num%i==0)
{
num/=i;
}
if(num==1)
{
num=i;
break;
}
}
else
{
i++;
}
}
printf("%lu",num);
评论
[c] 600851475143mpfexample.c:25:5: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘int’Floating point exception (core dumped)i600851475143iINT_MAX0600851475143%0