我正在FreeCodeCamp.org上学习一门课程,其任务是找到“最小公倍数”。所以我想出了一个我认为可行的解决方案,并且在一定程度上做到了。然后,代码似乎崩溃了。这是我的代码:
function smallestCommons(arr) {
arr = arr.sort((a,b) => {return a - b;});
console.log(arr);
var truesec = false;
for(var a = arr[1]; truesec != true; a++){
for(var e = 1; e <= arr[1]; e++){
//console.log(a % e + " " + e);
if(a % e != 0){
truesec = false;
break;
}else{
truesec = true;
}
}
//console.log(truesec + " " + a);
if(truesec == true){
return a;
}
}
return a;
}
console.log(smallestCommons([23,18]));
这应该根据他们的清单返回
6056820
,但是每次我检查到不同的结果时,我都会从同一代码中得到114461
和122841
。有人可以告诉我这有什么问题吗?如果有帮助,这是作业:
Intermediate Algorithm Scripting: Smallest Common Multiple
最佳答案
对于这个问题,我将采取另一种方法:
创建函数以获取所有主要因素
创建a[0]
和a[1]
之间所有数字的素数数组
将阵列减小为每个素数的最大功率。
乘以数组中剩余的所有素数
当O(k*a[1])
是答案时,您的方法将采用k
-并且k
可能会很高...这种方法将采用O((a[1])^2)
考虑以下代码:
function smallestCommons2(arr) {
arr.sort((a,b) => {return a - b;});
let factors = [];
for(let i = arr[0]; i <= arr[1]; i++)
factors.push(findPrimeFactors(i));
let reduced = reduceFactors(factors);
let ans = 1;
for (let i in reduced)
ans *= Math.pow(i, reduced[i]);
return ans;
}
function reduceFactors(factorsArr) {
let factorObject = {};
for (let i in factorsArr) {
for(let key in factorsArr[i]) {
if (!(key in factorObject) || factorObject[key] < factorsArr[i][key])
factorObject[key] = factorsArr[i][key];
}
}
return factorObject;
}
function findPrimeFactors (num) {
var primeFactors = [];
while (num % 2 === 0) {
primeFactors.push(2);
num = num / 2;
}
var sqrtNum = Math.sqrt(num);
for (var i = 3; i <= sqrtNum; i++) {
while (num % i === 0) {
primeFactors.push(i);
num = num / i;
}
}
if (num > 2)
primeFactors.push(num);
let factorObject = {};
for (let item of primeFactors) {
if (item in factorObject)
factorObject[item] += 1;
else factorObject[item] = 1;
}
return factorObject;
}
console.log(smallestCommons2([23,18]));
此代码将在秒内输出
6056820
编辑-找到post可以更好地完成相同操作
关于javascript - 最小公倍数-for循环分解-javascript,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/53978622/