網(wǎng)上看到這個(gè)問(wèn)題的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){//到達(dá)n了颖医，就沒(méi)有繼續(xù)的必要了位衩，已經(jīng)最大
return n;
}
if(n%i==0){//
n = n/i;
break;
}
}
}
return 0;
}
分析一下這個(gè)算法的復(fù)雜度，如果n=xa*yb*z^c,循環(huán)共運(yùn)行ax+by+cz次熔萧，也就是所有的素因數(shù)之和糖驴。這個(gè)值是<=n的。
思考了一下佛致，做了一些優(yōu)化：
- 對(duì)于每一個(gè)素因數(shù)贮缕，可以一次整除多次，避免每次從2開始數(shù)
- 從2開始俺榆，但避開其他偶數(shù)
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開始感昼，但避開其他偶數(shù)
if (n==i){//到達(dá)n了，就沒(méi)有繼續(xù)的必要了罐脊，已經(jīng)最大
return n;
}
if(n%i==0){//
while(n%i==0 && n>i)
n = n/i;
break;
}
}
}
return n;
}
把運(yùn)行次數(shù)減少到a+x/2+b+y/2+c+z/2定嗓，最壞情況下=n/2蜕琴。
就在剛才，看到一個(gè)greatim的idea宵溅，記錄當(dāng)前查找到的素因數(shù)min凌简，每次c從此開始，則運(yùn)算次數(shù)為 max{x,y,z}/2+a+b+c恃逻，當(dāng)然最壞情況下還是=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;
}
如果我們?cè)诰幊糖翱梢宰鲆恍?zhǔn)備，知道數(shù)x之前的素?cái)?shù),假設(shè)有pi(x)個(gè)寇损。如果n=xa*yb*z^c,那么運(yùn)行次數(shù)至少可以減少到max{pi(x),pi(y),pi(z)}+a+b+c畔派，當(dāng)然最壞情況下還是=n/2。
如果把n表示為2^k次方润绵，則以上算法的復(fù)雜度達(dá)到了O(exp(k))的(由數(shù)論知pi(n)~n/log(n))线椰。更高效的因式分解法是篩法。目前還沒(méi)有已知的算法可以在多項(xiàng)式時(shí)間內(nèi)對(duì)一個(gè)大數(shù)進(jìn)行因式分解尘盼。大數(shù)的因式分解是RSA加密算法的基礎(chǔ)憨愉。
