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

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

• "can be divided" or "can divide"? The description claims first, but the code achieve the second. – vnp Jun 21 '17 at 22:01
• FYI, GCF is usually called GCD -- Greatest Common Divisor. – Barmar Jun 22 '17 at 0:32

# Formatting

## 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) {
}
}


## Avoid explicit booleans when possible

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

• 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.