【一个数学问题】整数600851475143的最大质因子是什么？

1万 · 2014-10-16 09:17

本帖最后由 keer_zu 于 2014-10-17 11:45 编辑

0
整数13195的质因子是：5,7,13,29，其最大质因子是29.

那么问题来了，整数600851475143的最大质因子是什么？

1万 · 2014-10-16 09:17

#include <stdio.h>

int IsPrime(long long num)
{
long long i;

if(num == 0){
printf("err num!\n");
return -1;
}

if(num == 1 || num == 2)
return 0;

for(i = 2;i < num;i ++){
if(num % i == 0)
return -1;
}

return 0;
}

int main(void)
{
//long long Num = 13195;
long long Num = 600851475143;
long long i = 2;
long long pre_i = 2;

for(;i < Num;i ++){
if(IsPrime(i) == 0){
if(Num % i == 0){
if(i > pre_i){
printf("%d \n",i);
pre_i = i;
}
Num = Num/i;
i = 2;
}
}
}
printf("%d\n",Num);
}