DEV Community: Liam Foster

GCD and LCM Explained: Two Tricks That Make Number Problems Easy

Liam Foster — Sat, 03 Oct 2026 18:58:43 +0000

Two of the most useful ideas in basic math are the greatest common divisor (GCD) and the least common multiple (LCM). They show up in school homework, coding interviews, and everyday puzzles like figuring out when two repeating events line up. This guide explains both with simple examples you can do in your head.

The GCD of two numbers is the largest number that divides both of them evenly. For 12 and 18, the common divisors are 1, 2, 3, and 6, so the GCD is 6. Listing every divisor works for small numbers, but there is a smarter way for bigger ones: Euclid's algorithm.

Euclid's algorithm is over two thousand years old and still the fastest simple method. To find the GCD of 48 and 18, divide 48 by 18 and take the remainder: 48 = 2 x 18 + 12. Now replace the pair (48, 18) with (18, 12) and repeat: 18 = 1 x 12 + 6. Repeat again with (12, 6): 12 = 2 x 6 + 0. When the remainder hits zero, the last non-zero remainder is the GCD. So GCD(48, 18) = 6.

The LCM is the flip side: the smallest number that is a multiple of both. For 4 and 6, the multiples of 4 are 4, 8, 12, 16, and the multiples of 6 are 6, 12, 18, so the LCM is 12. Here is the trick that saves you from listing: LCM(a, b) = (a x b) / GCD(a, b). For 4 and 6, that is (4 x 6) / 2 = 12. Compute one, get the other free.

Let us try a bigger pair by hand: 36 and 48. Euclid's algorithm: 48 = 1 x 36 + 12, then 36 = 3 x 12 + 0, so GCD = 12. Then LCM = (36 x 48) / 12 = 1728 / 12 = 144. Check it: 144 / 36 = 4 and 144 / 48 = 3, both whole numbers. Correct.

Where does this come up in real life? Adding fractions needs a common denominator, which is the LCM of the denominators. Simplifying a fraction to lowest terms means dividing top and bottom by their GCD. Two buses that leave every 12 and 18 minutes meet every LCM(12, 18) = 36 minutes. The same idea schedules tasks, syncs animations, and compresses data in code.

If you want to double-check your hand calculations or work with larger numbers, Factor Calculator factors any number instantly and makes GCD and LCM practice much faster.

Learn Euclid's algorithm once, remember the GCD-to-LCM formula, and these problems stop being work and start being fun.

Prime Factorization Made Simple: Breaking Numbers Into Primes

Liam Foster — Sat, 03 Oct 2026 18:57:58 +0000

Every whole number is built from smaller building blocks called prime factors. Prime factorization is the process of breaking a number down into the prime numbers that multiply together to make it. For example, 60 = 2 x 2 x 3 x 5. Once you see the pattern, it becomes a satisfying little puzzle.

Why does this matter? Prime factors are the DNA of a number. They let you simplify fractions quickly, check whether a number is divisible by something, and understand how numbers relate to each other. Cryptography - the math that keeps your passwords and bank details safe - leans on the fact that factoring huge numbers into primes is extremely hard for computers.

The simplest way to factor a number by hand is the division method. Start with the smallest prime, 2, and divide as long as the result stays whole. Then move to 3, 5, 7, and so on. Take 84: divide by 2 to get 42, by 2 again to get 21, then 21 is not even so try 3 - 21 divided by 3 is 7, and 7 is prime. So 84 = 2 x 2 x 3 x 7.

A factor tree works the same way visually. Write the number at the top, split it into any two factors, and keep splitting each branch until every branch ends in a prime. Both methods always give the same answer, because of the Fundamental Theorem of Arithmetic: every integer greater than 1 has exactly one prime factorization.

You only need to test primes up to the square root of the number. If nothing divides it by then, the number itself is prime. This single trick cuts the work dramatically for big numbers.

Practice makes it quick. Try 120 on paper: 120 = 2 x 60 = 2 x 2 x 30 = 2 x 2 x 2 x 15 = 2 x 2 x 2 x 3 x 5. When you want to check your hand work or factor larger numbers instantly, a free tool like Factor Calculator shows the full factorization in seconds.

Once you are comfortable with prime factors, ideas like greatest common divisors and least common multiples become almost obvious - and your mental math gets noticeably faster.

Finding all factors of n in O(sqrt(n)) with a tiny JS function

Liam Foster — Sat, 03 Oct 2026 10:12:37 +0000

Quick one for beginners: you never need to test past the square root. Each divisor found below sqrt(n) gives you its pair for free, which is why a simple loop up to Math.sqrt(n) is enough. I built a small reference page around this idea here: factor calculator. Handy when you want to sanity-check homework without doing the loop by hand every time.