- 01Getting Started
- 02Your First Output (echo)
- 03Working with Variables
- 04Conditionals (if statements)
- 05Loops (for statements)
- 06Writing a Function
- 07Working with Arrays
- 08Loops (while statements)
- 09Classes (Object-Oriented Programming)
- 10Error Handling (try...catch)
- 11Handy Array Functions
- 12Recursive Functions
- 13Using the Standard Library
- 14The switch Statement
- 15The Ternary Operator
- 16Inheritance (Extending a Class)
- 17Writing Comments
- 18Logical Operators (AND, OR, NOT)
- 19Constants (define / const)
- 20Splitting and Joining Strings (explode, implode)
- 21Writing Null-Safe Code (the ?? operator)
- 22Searching an Array (in_array)
- 23Transforming an Array (array_map)
- 24Two-Dimensional Arrays (Tabular Data)
- 25Writing a Custom Exception Class
- 26Default Parameter Values
- 27Using an Array as a Set (Duplicate-Free Data)
- 28Checking Correctness (Your First Step into Testing)
- 29Higher-Order Functions (Passing a Function as an Argument)
- 30Stacks and Queues (Basic Data Structures)
- 31Type Conversion (Casting) Basics
- 32Intro to Regular Expressions (Pattern Matching)
- 33The Binary Search Algorithm
- 34Building a Caesar Cipher (a Character-Shifting Cipher)
- 35Understanding How Bubble Sort Works
- 36Building and Displaying Dates (Basic Year/Month/Day Operations)
- 37Writing Multiple Test Cases Together
- 38Speeding Up Calculations with Memoization (Caching)
- 39Normalizing Strings (trim, Unifying Case)
- 40Shallow Copy vs. Deep Copy
- 41Enum (Enumerated Types) Basics
- 42Flattening an Array
- 43Reversing a String and Checking for Palindromes
- 44Pairing Up Two Arrays (the zip operation)
- 45Rounding Numbers (floor, ceil, round)
- 46Multi-Line Strings (Heredoc)
- 47Functions That Return Multiple Values (Arrays and list())
- 48Finding the GCD and LCM (the Euclidean Algorithm)
- 49Formatting Numbers (Padding Digits, Decimal Places)
- 50Cleanup Logic with try/catch/finally
- 51Functions That Work with Any Type
- 52File Reading and Writing Basics
- 53Generating Random Numbers
- 54Bitwise Operators (AND, OR, XOR, shifts)
- 55Reading Command-Line Arguments
- 56Waiting for a Fixed Amount of Time (sleep)
- 57Watch Out for Floating-Point Rounding Errors
- 58Reading from Standard Input
- 59FizzBuzz (the Classic Practice Problem)
- 60Checking Whether a Number Is Prime
- 61Set Operations with Arrays (Union, Intersection, Difference)
- 62Converting Number Bases (Binary, Hex)
- 63Checking Balanced Parentheses (an Application of Stacks)
- 64Checking Whether Two Words Are Anagrams
- 65Checking Whether a Year Is a Leap Year
- 66Converting Temperature (Celsius to Fahrenheit)
- 67Prime Factorization
- 68[Applied] Build a Simple Inventory Management Tool
Finding the GCD and LCM (the Euclidean Algorithm)
In this lesson you will find the greatest common divisor and least common multiple with the Euclidean algorithm, getting hands-on with recursion. This is for anyone searching for "PHP how to find the GCD".
The Euclidean algorithm is an ancient, efficient way to find the greatest common divisor (GCD) of two numbers. You repeat "divide the larger by the smaller and carry on with the remainder" until the remainder reaches zero.
The sample code has gcdFunc($a, $b) call itself as gcdFunc($b, $a % $b) until $b === 0. The least common multiple (LCM) then comes from ($a * $b) / gcdFunc($a, $b) - notice how the two algorithms connect.
A common stumbling block for beginners is why that formula gives the LCM at all. Knowing the mathematical relationship - the product of the two numbers divided by their GCD - turns rote memorisation into real understanding.
It is a good exercise that builds algorithmic intuition, and a very popular subject for practising recursion. It is a famous algorithm that packs in the fundamentals of both mathematics and programming.
๐งช This site can't compile or run PHP directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser โ nothing is sent anywhere).