# Feedback on Smallest Common Multiple: Prime Factorization Method

I approached this problem with an elementary method using prime factorization. After looking at the solutions that freecodecamp gives I realize there was a much more sophisticated method of doing this with a Euclidean algorithm.

Nonetheless my code still works even though it’s a 100+ lines of code and much less efficient. I wrote it in a way that was intuitive to me, hoping a stranger could understand it. If you were to solve this problem using prime factorization would you have written your algorithm the same way? Or do you think my code is way too messy and incomprehensible? How would you have written cleaner code?

Thanks!

Your code so far

``````
/*
1. Factorize each number in array.
a) For each number, find all prime numbers up to n
b) Get modulus of n from each of its prime numbers, p
b-1)  n%p != 0 for all p? Then n is prime. Collect in a factorization array.
b-2) n%p === 0 for some p? Then n is not prime.
i.) Divide n by this p and feed it back into step 1.
2. Find greatest occurence of each prime number overall in the factorizations and multipy together to find LCM
*/

//Find all prime numbers up to and including num
function getPrimes(num) {

if (num < 2) { return null; }

//List all integers from 2 up to num
let list = Array.from(new Array(num - 1), (val, index) => index + 2);

//Iterate through the list and eliminate numbers that are mutiples of the current element
for (let i = 0; i < list.length; i++) {
let div = list[i];
list = [...list.filter((elem) => elem % div !== 0 || elem === div)];
}

return list;
}

//Factorize a number n and store its factors in an array "factors"
//Should intilially be called with only the first parameter. The second parameter is used behind the scenes in recursion.
function factorize(n, factors = []) {

let primes = getPrimes(n);

if (!primes) {
return factors;
}

//If n is prime
if (primes.every(p => n % p != 0)) {
factors.push(n);
}
//If n is not prime keep factorizing recursively
else {
//Find the first multiple of n
let first = primes.find(p => Number.isInteger(n / p));
factors.push(first);
factorize(n / first, factors);
}

return factors;
}

//Get unique numbers in an arr
function getUnique(arr) {

let unq = [];
arr.forEach(elem => {
if (!unq.some(x => x == elem)) {
unq.push(elem);
}
});

return unq;
}

//Count the number of times a unique number appears in the factorization
function countUnique(factors, unq) {

//Initialize count array for unique factors
let count = new Array(unq.length).fill(0);

unq.forEach((u, index) => {
//Count how many times u appears in the factorization
factors.forEach(f => {
if (f == u) {
count[index]++;
}
});
});

return count;
}

//Main
function smallestCommons(arr) {

//Expand arr
let last = Math.max(...arr),
first = Math.min(...arr);
let narr = Array.from(new Array(last - first + 1), (val, index) => index + first);

//Factorize each number in narr and store results in objArr
let objArr = [];

narr.forEach(num => {
let factors = factorize(num);
let u_arr = getUnique(factors);
let c_arr = countUnique(factors, u_arr);

//At this point we don't care about which factors belong to which numbers. We only care about the highest count
for (let i = 0; i < u_arr.length; i++) {
objArr.push({ factor: u_arr[i], counts: c_arr[i] });
}

return;
});

let lcmFactors = getUnique(objArr.map(obj => obj.factor));

//Multiply each factor by itself the greatest number of times it appears
let multiples = lcmFactors.map(elem => {
let fCounts = objArr.filter(obj => obj.factor == elem)
.map(obj => obj.counts);

return elem ** Math.max(...fCounts);
});

return multiples.reduce((lcm, elem) => lcm * elem, 1);
} //End of smallestCommons

console.log(smallestCommons([2, 10]));
console.log(smallestCommons([1,5]));

``````

User Agent is: `Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_3) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/80.0.3987.163 Safari/537.36`.

Challenge: Smallest Common Multiple

Link to the challenge:

To be honest, if I had this problem dropped in my lap, the first thing I would do is google ‘find smallest common multiple’. Not because I am looking for JS code someone has already written but rather to familiarize myself with the algorithm. Once I had an understanding of what to do then I would implement it in code. I don’t think there is anything wrong with brushing up on algorithms like this before you begin typing. We can’t know everything, and even if you did know it at one time, if you haven’t used it in years then chances are you don’t know it as well as you think you do.

As far as your code, I’m counting 5 functions. Experience tells me right there that the solution is overly verbose/complex for such a problem. I commend you for gutting this out and only using the knowledge off the top of your head to solve this, but now that you know there is a better way to solve this I would recommend you revisit this in a few days and try using that method.

Bottom line, don’t be afraid to use the vast amount of resources available to you right at your fingertips. Your code will only be as good as your understanding of the problem.

2 Likes

Thanks for your input @bbsmooth. I totally agree with familiarizing yourself with the material first. Problem is I picked the wrong method and came up with a messy algorithm . Went back and wrote much more efficient code today.

``````//Least common multiple (lcm) of an array of numbers
//Method 2: Using the greatest common divisor (gcd)
//			lcm(a,b) = (a*b)/gcd(a,b)
//lcm is recursive:
//			lcm(x_1, x_2, ..., x_n) = lcm{ lcm[ (x_1, x_2,..., x_n-1), x_n ] }
//			https://en.wikipedia.org/wiki/Least_common_multiple#Other

function smallestCommons(arr) {

//Expand arr in descending order
let max = Math.max(...arr);
let list = Array.from(new Array(Math.abs(arr[1] - arr[0]) + 1), (val, index) => max - index);
//console.log(list);

//Greatest common divisor of two numbers
const gcd = (x, y) => y === 0 ? x : gcd(y, x % y);

//Least common multiple of two numbers
const lcm = (a, b) => a * b / gcd(a, b);

let i = 1;
let testLCM = max;

do {
let listLCM = lcm(testLCM, list[i]);
//console.log(`loop \${i}; lcm(\${testLCM},\${list[i]})`);

//If testLCM is a multiple of the rest of list then we've found listLCM
if (list.slice(i + 1).every(x => listLCM % x === 0)) {
return listLCM;
}
//Continue searching for list LCM
else {
testLCM = listLCM;
}

i++
}
while (i < list.length);

}

//Test here
console.log(smallestCommons([23, 18])); //n loops = 50
``````