Math: Finding GCF and LCM Using Continuous Division (Translated to JavaScript)

Hi!

In this, I'll show a method other than factorisation and clustering the factors to find GCF (Greatest Common Factor) and LCM (Least Common Multiple).

I assume you're familiar with the first method. That is using factor tree and then grouping the results. I was taught to do this method in elementary school. The method has already been translated to an application on Port Raptor: GCFLCM.C.

---

Let's start to implement the continuous division method.

For example, we want to find GCF and LCM from:

8, 16, 18

Method:

1. Create a table and write down those numbers as first row. Give some space for vertical column on the leftmost. The leftmost column will be used to list the divisor. The cells between the first row and first column are the division results (quotients). The division goes diagonally.
2. Start with the division with 1, well...
3. Then, divide starting from the lowest prime number → 2.
4. If an element (or elements) can't be divided with current prime divisor, but other element (or elements) can be divided, put the original element(s) which can't be divided to the next division result cell. Or, for element which can't be divided, leave it intact.
5. Increment the divisor to higher prime number if ALL division result can't be divided with current prime number.
6. Do it repetitively until the division result of each number is uniformly one (1).
7. For each row which ALL elements can be divided (no remainder), include the divisor(s) as GCF.
8. For each row which SOME (at least one) elements can be divided AND ALL elements can be divided, include the divisor(s) as LCM.

---

AS SUCH

NUMBER → DIVISOR ↓	8	16	18
1	8	16	18
2	4	8	9
2	2	4	9
2	1	2	9
2	1	1	9
3	1	1	3
3	1	1	1

WITH MARKERS

WHICH ONE IS GCF?

From the table above, look at the leftmost column, the divisor (or I colorfully wrote that as divider on the image). The ones which can divide ALL elements (numbers) are included as GCF.
Those are 1 and 2 → 1 × 2 = 2.

WHICH ONE IS LCM?

Look again at the divisor column, the ones which can divide SOME elements (at least one element) AND can divide ALL elements are included as LCM.
In another words, ALL numbers on the divisor column.
Those are 1, 2, 2, 2, 2, 3, and 3.
Multiply all of those → 1 × 2 × 2 × 2 × 2 × 3 × 3 = 144.

---

RESULT SUMMARY

Therefore, using the continuous division above:

For these numbers → 8, 16, 18

GCF = 1 × 2 = 2

LCM = 1 × 2 × 2 × 2 × 2 × 3 × 3 = 144

---

As you can see from above example, it's straightforward to determine the LCM:

LCM ➡️ Multiply ALL the divisors.

Now, about the 1 as the first divisor: it is to accommodate GCF.

For instance:

2 and 3.

Both are prime numbers.

The GCF will be ➡️ 1 ✅

The LCM will be ➡️ 1 × 2 × 3 = 6 ✅

We can try these 2 and 3 using the table method. If it is done correctly, it will yield similar result as the calculation above.

---

MORE EFFICIENT

This is much more direct rather than the factor tree technique, which is then continued by grouping/clustering the factors. It is way more efficient and we certainly can put as many numbers as we need.

---

TRANSLATION

I first found this continuous division technique from a school textbook when I was tutoring. I was the tutor. The tutee was a boy, he was actually brilliant — I was simply there.

I flipped his books randomly and I found that. Hm! 👀

So then, I translated it to JavaScript (JS). The JS coding can also be translated to other languages surely.

I made a flowchart of the method. I hope the chart explains the flow.

High five to draw.io for the flowchart.

The flowchart above is the interconnected quantisation of the continuous division technique.

---

JAVASCRIPT FUNCTION

The function name is glc

It receives an argument. That is an array of positive integers, which each is greater or equal to 2, to 1,000,000 (1 million).

The minimum array length is 2, maximum is 20.

This (rewritten) function definition below is actually used in the demonstration below this post and it was thoroughly tested (test was helped by ChatGPT).

For full context, above response from ChatGPT was from my oopsie using \b (word boundary) as regex (wrong) pattern as the demo app input capturer below. As it didn't work as intended, ChatGPT analysed it, and Hey, no need for that boundary, then I responded, Ah thanks. Indeed I need to remove the \baboon part.

---

HOW TO USE

Run:

glc([array_of_positive_integers]);

Example:

glc([8, 16, 18]);

---

ARRAY INPUT

Input must be an array of positive integers with minimum array length of 2 and maximum length of 20.

Each array item must be below 1,000,000 (1 million).

---

OUTPUT

For valid input, the output will be an Object. It consists of:

{ duration: string, input: [ORIGINAL_INPUT_ARRAY], output: { gcf: integer, gcf_array: [GCF_FACTORS_LIST], lcm: integer, lcm_array: [LCM_FACTORS_LIST] } }

For example:

glc([8, 16, 18]); /* OUTPUT { duration: "1 ms", input: [8, 16, 18], output: { gcf: 2, gcf_array: [1, 2], lcm: 144, lcm_array: [1, 2, 2, 2, 2, 3, 3] } } */

For invalid input, the output will be error String.

---

ACCESSING PARTICULAR OUTPUT'S ITEM

const input = [8, 16, 18]; const output = glc(input); /* // Example on how to differentiate error output. const isError = typeof output === "string"; // The methods below are with the assumption that the // output above is an Object type. */ const duration = output.duration; // String const original_input = output.input; // Array of original input const result = output.output; // Object output const gcf = result.gcf; // Positive integer const gcf_array = result.gcf_array; // Array const lcm = result.lcm; // Positive integer const lcm_array = result.lcm_array; // Array /* // Or, using object destructuring assignment. const { gcf, gcf_array, lcm, lcm_array } = result; */

---

DEMONSTRATION

Use comma/space to delimit each number, as in 2, 6, 18 or 2 6 18.

NENA - 99 Luftballons

---

Thanks for stopping by, and bye, see you again.