[Solved] Help with Smallest Common Multiple algo challenge

[Solved] Help with Smallest Common Multiple algo challenge
0.0 0

#1

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;
      });

}

#2

I would focus on the process he describes at 00:24.


#3

Oh my, my mistake - I linked to the wrong video in my original post. This is the method I was referring to. I will edit my original post.

Around 1:40 he describes the selection process. That’s what I want to build in logic. I’m not sure how to go about it, other than creating another array/object - a sort of number:count matrix.


#4

Or, in light of more direct / efficient solutions, the prime factorization method may be futile and should be scrapped?


#5

Well, neither of the processes in those videos differ in any meaningful way (the second video is just more descriptive).

Anything other than Euclid’s algorithm is going to be unbearably inefficient. You’ve pursued a concept and found some limitations, which is great experience (it’s what these challenges are all about, IMHO). I think that it is possible to continue with what you’ve done so far, but there are far better uses of your time, so it’s best not to dwell.


#6

This was my suspicion. It’s an answer I both wanted and didn’t want to hear. I wanted to see this through. There’s probably a catchy saying to better describe it, but bad ideas acquire a sort of inertia once you’ve invested significant time in them.

Thank you for the replies.