Need Help finishing Smallest Common Multiple. Am almost there

Need Help finishing Smallest Common Multiple. Am almost there
0.0 0

#1

I’m able to find the common multiples of most numbers except large ones like the last two numbers ([23,18]) using my code. How do I get my code to check for multiples that are in the millions, which is the multiple for the above numbers?

I have not yet created a way to see if all common multiples are divisible by the range between the given variables because I’m still looking for a way to find how to check for multiples that are in the millions…

My code:


/* jshint esversion: 6 */ 

function smallestCommons(arr) {
  var list = arr.sort(function(a, b){return b-a;});//returns big to small
  var f=list[0]+1; //first num +1
  var l=list[1]; //second num
  var start = list[0];
  var end = start*start;  
  
  var newlist = []; //new list range from big to small
    while (l<f){
      f--;
      newlist.push(f);
    }

  var firstlist = [];
  var secondlist = [];

  do {
    start++;
    var firstmultiple = start*newlist[0]; //returns 23 * number up to end
    var secondmultiple = start*newlist[1]; // returns 22 * number up to end
      firstlist.push(firstmultiple); //outputs array for 23
      secondlist.push(secondmultiple); //outputs array for 22
  }
  while (start<end); 

//filter between firstlist array and secondlist array
  var findnum = firstlist.filter((val) => {
  for (var i=0;i<secondlist.length;i++) {
        if (val == secondlist[i]) {
          return true; 
      } 
  }
});
  
// returns common multiples for both numbers
  return findnum;
}


smallestCommons([23, 18]);

#2

What happens when you run the code for this example? I’m guessing the program just hangs (i.e. takes too long to execute and freezes before it finds the answer?).

It looks to me like you’ll need a more efficient algorithm to produce the answer. Can you think of any way to do this exercise more efficiently than your current approach? As a hint: You may want to look into ‘Prime Factors’. :slight_smile:

Let me know if you’re still stuck!


#3

Thanks for the tip, and yes it just hangs there because the algorithm isn’t efficient for large calculations. I’ll give the prime factors a try and see if I can get this working in the next week or so between projects. Best.


#4

Hi Gkleinereva. I did some tweaking and got much closer this time. After doing more research I realized I took the long path to solving this. I should have and could have started with Euclidean’s Algorithm but didn’t find that in my initial research. I decided to continue writing my code even though it’s the longer way. My new code gets all the lowest common factors for range between all the provided numbers. The only thing I need to figure out now is how to cancel the right numbers in the concated array in order to multiply them to get the LCM. Any ideas?

/* jshint esversion: 6 */ 

function smallestCommons(arr) {

  var list = arr.sort(function(a, b){return a-b;});//returns small to big
  var f=list[0]-1; //first num
  var l=list[1]; //second num
  var newlist = []; 
  //new list range from small to big
    while (f<l){
      f++;
      newlist.push(f);
    }
          //Check if num is prim
          function CheckIfPrime(value) {  
            var high = Math.floor(Math.sqrt(value)) + 1;  
            for (var div = 2; div <= high; div++) {  
                if (value % div == 0 && value !=2) {  
                    return false;  
                }  
            }return true;  
        } 
          //Check if num is not prim
          function NotPrime(value) {  
            var high = Math.floor(Math.sqrt(value)) + 1;  
            for (var div = 2; div <= high; div++) {  
                if (value % div == 0) {  
                    return true;  
                }  
            }return false;  
        } 
          var primes = newlist.filter(CheckIfPrime);
          var notprimes = newlist.filter(NotPrime);
  
var finalnums = [];  
  // if num divisible by 2 (except 2) divide it down and push num 2 along w/ results
  for (var i=0;i<notprimes.length;i++) {
    while(notprimes[i] % 2 == 0 && notprimes[i] !=2) {
      notprimes[i] = notprimes[i]/2;        
      finalnums.push(2,notprimes[i]);
   }
  // if num divisible by 3 (except 3) divide it down and push number 3 along w/ results
    while(notprimes[i] % 3 == 0 && notprimes[i] !=3) {
       notprimes[i] = notprimes[i]/3;       
      finalnums.push(3,notprimes[i]);
   }
 }
  //loop through non-primes
  //Filter out remaining divisible numbers
  //Returns an array of smallest common factors of non-primes nums
   var findnum = finalnums.filter((val) => {
    for (var k=0;k<notprimes.length;k++) {
        if (val == notprimes[k] || val == 2) {
          return true;  
    } 
   } 
return false;
});
  
return findnum.concat(primes);
  

}


smallestCommons([1, 13]);



#5

I wasn’t able to find a practical method of cancelling out the appropriate numbers in my array to find the LCM, so I adopted Euclidean’s Algorithm. Using some other tips I found I created three functions that do the trick:

/* jshint esversion: 6 */ 

function smallestCommons(arr) {
  var list = arr.sort(function(a, b){return b-a;}); //sorts big to small
  var a=list[0];
  var b=list[1];
  
 // finds greatest common divisor given a and b - Euclidean’s Algorithm
  function GCDiv(a,b){
   if(a%b == 0) {
    return b; 
   } else {
    do { 
        var r = a%b; // 23%18==5, 18%5==3, 5%3=2, 3%2=1, 2%1=0 LAST iteration
        a = b; // a = 18, a = 5, a = 3, a = 2, a = 1 LAST Found remainder not != 0
        b = r;  // b = 5, b = 3, b = 2, b = 1
      } while (b !=0); {
        return a; // returns last remainder while b is not equal to zero
      }
   }  
  }
  // returns lowest common multiple between two numbers
  function LCMofTwo (a, b){
    return (a*b) / GCDiv(a,b);
  }

  var newlist = [];
  var startnum = list[0]+1;
  var endnum = list[1];
  //creates a range from given numbers big to small
  while (startnum>endnum){
      startnum--;
      newlist.push(startnum);
    }
  
  function FinalLCM () {
    var finalmultiple = 1;
    // iterate through provided range
    for (var i=0; i<newlist.length;i++) {
    // sets finalmuliple equal to result of lowest common multiple of two nums
      //while iterating from left to write one number at a time
      finalmultiple = LCMofTwo(finalmultiple, newlist[i]);
    }
    // returns final numbers once loop reaches the last num in the range
    return finalmultiple;
  }
  return FinalLCM (arr);
  
}
smallestCommons([23, 18]);