euler 3: Largest prime factor

题出自 Project Euler Problem 3:
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！！！