Finding the greatest common factor of a list of numbers in JavaScript

Question

The goal of this code is to take an array of two or more positive integers and return their greatest common factor, or GCF. (This is the biggest number that can be divided into all the numbers in the array without any remainder).

I feel like my code is much too long and complicated. Surely there's a more efficient way to do this. Also, I know it's best practice to avoid global variables, and I used one here.

Codepen

/* Test whether a number is a factor of another number */
function isFactor(num, fact){
    if(num % fact == 0){
        return true;
    }
    else{
        return false;
    }
}

/* List all the factors of a number */
function listFactors(number){
    factors = [1];
    var i = 2;
    while(i <= number){
        if(isFactor(number, i)){
            factors.unshift(i);
        }
        i++;
    }
    return factors;     
}

var toTest = 1;

/* Find the GCF (greatest common factor) of the numbers in an array */
function GCF(intList){
    var GCF = 1;
    var factorsOfEach = [];
    for(item in intList){
        var num = intList[item];
        var factors = listFactors(num);
        factorsOfEach.push(factors);
    }
    var count = 0;
    factorsOfFirst = factorsOfEach[0];
    var length = factorsOfFirst.length;
    while(count < length){
        var toTest = factorsOfFirst[count];
        var passTest = factorsOfEach.every(arrayContains);
        if(passTest){
            GCF = toTest;
            return GCF;
        }
        else{
            count += 1;
        }
    }
    return GCF
}

/* Check whether an array contains the variable "toTest" */
function arrayContains(array){
    if(array.indexOf(toTest) != -1){
        return true}
    else{
    return false}
}

Answer 1

Formatting

Before addressing optimizations, let's address some formatting problems

while vs. for loops

It is preferred to use a for loop when you:

1. Have an incrementer
2. The incrementer is not used outside of the loop
3. The incrementer is either strictly increasing or strictly decreasing

This is the case with both of your while loops. They can be refactored to the following:

In listFactors():

for (var i = 2; i <= number; i++){
    if(isFactor(number, i)){
        factors.unshift(i);
    }
}

In GCF():

for (var count = 0; count < factorsOfFirst.length; count++){
    var toTest = factorsOfFirst[count];
    var passTest = factorsOfEach.every(arrayContains);
    if (passTest) {
        return toTest;
    }
}

Avoid explicit booleans when possible

Instead of:

if(num % fact === 0){
    return true;
}
else{
    return false;
}

it is preferable to write:

return num % fact === 0;

and the same for your other functions.

Avoid global variables

As you correctly pointed out, you should try not to use mutable global variables; it makes the code much harder to understand. To avoid this, you could make the arrayContains function merely an arrow function and pass in toTest as well:

var testPassed = factorsOfEach.every(arr => arr.indexOf(toTest) !== -1);

A Cleaner Solution

Using the Euclidean Algorithm to find the GCD/GCF of two numbers (assuming non-negative numbers) is a much more cleaner and optimized approach:

function GCF(a, b) {
    if (b === 0) return a;
    else         return GCF(b, a % b);
}

Then, just use a reduce statement to apply GCF to all of the numbers in the array:

function findGCFofList(list) {
    return list.reduce(GCF);
}

Answer 2

• The sequence

  if(num % fact == 0){
      return true;
  }
  else{
      return false;
  }
  

  is a long way to say

  return num % fact == 0;
  

• A GCF(a, b, c) is GCF(GCF(a, b), c). In turn, a GCF of two numbers may and shall be computed via the Euclid's algorithm (or Stein's algorithm).

  The efficient approach is along the lines of pseudocode

  result = x[0]
  for n in x[1:]
      result = gcf(result, x[i])
      if result == 1
          break
  return result
  

  Factorizing individual numbers is a waste of time.