求一个整数的最大素因数

网上看到这个问题的Blog，看到他的解答：
cnblogs

int largest_prime_factor(int n){
int count=0;
if (n<1){//
return -1;
}
if (n==1){//判断边界条件
return 1;
}
while (n >1){
    for(int i=2;i<=n;i++){
        if (n==i){//到达n了，就没有继续的必要了，已经最大
            return n;
        }
        if(n%i==0){//    
            n = n/i;
            break;
        }
    }
 }
 return 0;
}

分析一下这个算法的复杂度，如果n=x^a*yb*z^c,循环共运行ax+by+cz次，也就是所有的素因数之和。这个值是<=n的。

思考了一下，做了一些优化：

1. 对于每一个素因数，可以一次整除多次，避免每次从2开始数
2. 从2开始，但避开其他偶数

    int largest_prime_factor(int n){
    assert(n>0);
if (n==1){//判断边界条件
return 1;
}
while (n >1){
        
for(int i=1;i<=n;i=i+2){ 
  if(i==1) i=2;//从2开始，但避开其他偶数  
      if (n==i){//到达n了，就没有继续的必要了，已经最大
  return n;
}
if(n%i==0){//
while(n%i==0 && n>i)
  n = n/i;
break;
}
}
}
return n;
    }

把运行次数减少到a+x/2+b+y/2+c+z/2，最坏情况下=n/2。

就在刚才，看到一个greatim的idea，记录当前查找到的素因数min，每次c从此开始，则运算次数为 max{x,y,z}/2+a+b+c，当然最坏情况下还是=n/2。

int largest_prime_factor(int n){
  int min;
if (n<1){//
return -1;
}
if (n==1){//判断边界条件
return 1;
}
min=2;
while(n%min==0)
  n=n/min;
if(n>1) min=3;
while (n >1){
for(int i=min;i<=n;i=i+2){
if(n%i==0){//
  min=i;
  n = n/i;
break;
}
}
}
return min;
}

如果我们在编程前可以做一些准备，知道数x之前的素数,假设有pi(x)个。如果n=x^a*yb*z^c,那么运行次数至少可以减少到max{pi(x),pi(y),pi(z)}+a+b+c，当然最坏情况下还是=n/2。

如果把n表示为2^k次方，则以上算法的复杂度达到了O(exp(k))的(由数论知pi(n)~n/log(n))。更高效的因式分解法是筛法。目前还没有已知的算法可以在多项式时间内对一个大数进行因式分解。大数的因式分解是RSA加密算法的基础。