I’ve been stuck on the Smallest Common Multiple challenge for a few days.
I know a lot of other threads use Euclid’s method / GCD to arrive at LCM. I am trying to solve it through prime factorization of all numbers in the range. The pen & paper method I have learned is to select the highest number of each prime to multiply together. Hard to explain in writing; easier by video:
Currently, my code successfully generates all the prime factors for each number in the series, but I’m not sure how to proceed from there. As in, what the logic should look like to “select” sets of primes based on count within a nested array.
Can the challenge be solved w/prime factorization?
Any help is appreciated.
Pen here: http://codepen.io/belcurv/pen/YNwoGb?editors=1012
Code:
/* to find LCM for more than 2 numbers, have to use prime factorization method
18 19 20 21 22 23
2, 3, 3 1, 19 2, 2, 5 3, 7 2, 11 1, 23
^ ^ ^ ^ ^ ^ ^ ^ ^
3 * 3 * 19 * 2 * 2 * 5 * 7 * 11 * 23 = 6056820
*/
function getPrimes(number) {
var i = 2,
primes = [];
while (i <= number) {
if (number % i === 0) {
primes.push(i);
number /= i;
} else {
i += 1;
}
}
return primes;
}
// find smallest common multiple
function smallestCommons(arr) {
// sort input array low to high
arr = arr.sort((a, b) => a - b);
// setup
var series = [],
primesArr;
// generate number series, inclusive of start & finish
for (var i = arr[0]; i <= arr[1]; i += 1) {
series.push(i);
}
// log working set
console.log('Input series: ' + series);
// build prime factors array
primesArr = series.map(function(num) {
return getPrimes(num);
});
// log primes array
console.log('Prime Factors: ', primesArr);
//
// NOT CORRECT
return primesArr
.reduce(function(a, b) {
return a.concat(b);
})
.reduce(function(acc, val) {
return acc * val;
});
}