# Code Challenge: Greatest Common Factor

Share the love

This week’s JavaScript code challenge again comes from Coderbyte:

Using the JavaScript language, have the function Division(num1,num2) take both parameters being passed and return the Greatest Common Factor. That is, return the greatest number that evenly goes into both numbers with no remainder. For example: 12 and 16 both are divisible by 1, 2, and 4 so the output should be 4. The range for both parameters will be from 1 to 10^3.

Here are some test cases:

Input = 7 & num2 = 3 -> Output = 1
Input = 36 & num2 = 54 -> Output = 18

Here’s my solution collapsed:

[code language=”javascript” collapse=”true”]
function Division( num1, num2 ) {
var gcf = 1;
var higher = num2;
var lower = num1;

if ( num1 > num2 ) {
higher = num1;
lower = num2;
};

for ( var i = 0; i < lower; i++ ) {
if ( lower % i == 0 && higher % i == 0 && i > gcf ) {
gcf = i;
};
};

return gcf;
};
[/code]

Before using both numbers, I actually setup a for loop just to find the greatest factor of the first number. First, I setup gcf to hold the number and set it to one initially. Then, I setup this for loop:

[code language=”javascript”]
for ( var i = 0; i < lower; i++ ) {
if ( lower % i == 0 && i > gcf ) {
gcf = i;
};
};
[/code]

This cycled over all of the numbers from 1 up to num1. If the remainder of num1/i was 0, it compared i to the current gcf value. If i was larger, gcf was set to i.

Now, I needed a way to incorporate the second number and find a commonality. First, I wanted to decrease the amount of computations possible. To do that, I could first start by finding the greatest common factor in the smallest number with the rationale that the gcf couldn’t be larger than the smallest number.

I setup variables for highest and lowest and arbitrarily set them to num2 and num1 respectively. Then, I had an if statement swap the values if necessary:

[code language=”javascript”]
var higher = num2;
var lower = num1;

if ( num1 > num2 ) {
higher = num1;
lower = num2;
};
[/code]

Finally, I built the second number into my original for loop by including `higher % i == 0` in the if block.

[code language=”javascript”]
for ( var i = 0; i < lower; i++ ) {
if ( lower % i == 0 && higher % i == 0 && i > gcf ) {
gcf = i;
};
};
[/code]

Now, the only time the if block runs is when i is a common factor between both the highest and lowest numbers.

Solve it a different way? Please share!

Share the love
Strategies on solving problems and wowing customers every Sunday 👉
Strategies for solving problems and wowing customers 👇