ACM数论基础训练题解之最大质因子

1.最大质因子

对于一个整数来说，如13195的因子有5,7,13,29，其中29是它的最大质因子，现在问题是这样的，600851475143的最大质因子是多少？

输入：

600851475143

输出：

6857

思路：一个数字n，如果n不能整除2到根号n的所有整数，那么n就是一个质数

代码：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
__int64 number,limit,maxnumber;
scanf("%I64d",&number);
maxnumber=0;
limit=(__int64)sqrt(number);
for(int i=2;i<=limit;i++)
if(number%i==0)
{
maxnumber=i;
while(number%i==0)
number/=i;
}
if(maxnumber==0)
maxnumber=number;
printf("%I64d",maxnumber);
return 0;
}