算法练习--整数拆分为素数乘积
浏览数：24 /
时间：2015年06月08日
问题：
输入6
输出 1*2*3
1. build素数表
2. 从素数表按次序取素数，n除素数，如果不能整除，素数表索引++，否则，n/=素数，继续判断
3. 遍历素数表
4. 有限性：素数表需要足够大 ，如果数字非常大，此算法需要改变
JS 实现：
function p(n){
if(n<2) {return 0;}
if(n == 2){return 1;}
for(var i = 2; i < n; i++){
if(n%i == 0){return 0;}
}
return 1;
}
var pl = new Array();
for(var i = 2,index = 0;index<100;i++){
if(p(i) == 1){pl.push(i);index++;}
}
function f(n){
var pIndex = 0;
var ret = "1";
for(;pIndex<100; ){
if( n % pl[pIndex] == 0){
ret += "*" + pl[pIndex];
n/=pl[pIndex];
}
else{
if(p(n)){
ret += "*" + n;
return ret;
}
pIndex ++;
}
}
return ret;
}
console.log(f(111223));
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
