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

Hi!

In this, I'll show a method other than factorization 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 tree factors and then grouping the dilly. I was taught to do this method in elementary school. The method has already been translated to an application on Port Raptor: GCFLCM.C. There's an explanation about the method flow on that post too.

---

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.
Basically, 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 easy to determine the LCM:

LCM ➡️ Multiply ALL the divisors.

Now, about the 1 divisor part. It is to accommodate GCF.

For instance: 2 and 3. Both are prime numbers.

The GCF will be 1. LCM will be 1 × 2 × 3 = 6.

You can try (prove) it out using the table method above.

---

MORE EFFICIENT

This is pretty much a direct method, rather than using tree factors and grouping/clustering. It's way more efficient and we can put as many numbers as we need to calculate on the table.

---

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 just there for reasons. I flipped the papers randomly and I found that. WHOA, mate! 👀

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.

I'm not sure if that flowchart is 100% accurate. But that looks like the basic concept.

---

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

---

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