The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
我自己的解法思路是先判断该数（记为A）是否为prime，如果是，则直接返回它本身。否则从该数的一半开始（记为index)，判断index是否能被A整数以及index是否是prime，当两者同时满足时，返回index，否则index自减1。 判断某数是否为prime的算法，是从该数的平方根数开始一个一个检查。代码如下:
#include <stdio.h>
#include <math.h>
//#include <limits.h>
int is_prime(long l);
long largest_prime_factor(long l);
int main(int argc, char *argv[])
{
long result = largest_prime_factor(600851475143L);
printf("%ld\n",result);
return 0;
}
int is_prime(long l){
long l_sqrt = (long)sqrt(l);
long i = 2L;
for(; i <= l_sqrt; i++){
if(l % i == 0)
return 0; /* is not prime */
}
/* is prime */
return 1;
}
long largest_prime_factor(long l){
if(is_prime(l))
return l;
long l_mid = l/2;
long l_ind;
for(l_ind = l_mid; l_ind >=2; l_ind--){
if((l%l_ind == 0) && is_prime(l_ind))
return l_ind;
}
return 1; // never come here
}
上面的算法很惨，算了几十分钟都没有算出结果。所以最后我放弃了，google到了下面这个算法:
#include <stdio.h>
long largest_prime_factor(long l);
int main(int argc, char *argv[])
{
long result = largest_prime_factor(600851475143L);
printf("%ld\n",result);
return 0;
}
long largest_prime_factor(long l){
long factor = 2L;
while(l > 1L){
while(l % factor == 0 ){
l = l / factor;
}
factor++;
}
return (factor-1);
}
细想一下，这个算法与筛选法类似。但是，我怎么就没想到呢？FAIL！！！
