Problem 3--(c)

Problem 3

02 November 2001

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Answer:

6857

code:

解法1：

#include
int main(void)
{
long long int num=600851475143,res=2;
while(res!=num)
{
if(num%res==0)
num=num/res;
else
res++;
}
printf("%lld\n",res);
return 0;
}

解法2：

#include
#include
int prime(long long int n)
{
int flag=1;
long long int i;
for(i=2;i<=sqrt(n)&&flag==1;i++) if(n%i==0) flag=0; return (flag); } int main(void) { long long int i,j=600851475143,k,max; k=sqrt(j); for(i=3;i<=k;i=i+2) { if(prime(i)==1&&j%i==0) max=i; } printf("%lld ",max); return 0; }