Published by Dimitris Kougioumtzis · Updated
Use the Euclidean GCD to compute a / gcd(a,b) × b.
Divide out the GCD before multiplying to combine the prime-factor requirements of both integers.
When to use Least common multiple
Aligning periodic schedules and repeated cycles.
Choosing an alternative
GCD describes common divisibility; LCM describes common multiples.
Worked example: input and state changes
Example input
12, 18
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 12, 18 ], "active": [] }Step 1: 12 mod 18 = 12.
State at this checkpoint
{ "values": [ 12, 18 ], "active": [] }Step 2: 18 mod 12 = 6.
State at this checkpoint
{ "values": [ 12, 18 ], "active": [] }Step 3: 12 mod 6 = 0.
State at this checkpoint
{ "values": [ 12, 18 ], "active": [] }Step 4: Least common multiple = 36.
State at this checkpoint
{ "values": [ 36 ], "active": [ 0 ] }
Expected final state
Least common multiple = 36.
Complexity and input bounds
Family: Number theory. Time complexity: O(log min(a,b)).
Space complexity: O(1) auxiliary space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Two nonnegative integers up to 9999; LCM is 0 if either value is zero.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Multiplication before division can overflow unnecessarily; define zero-input behavior first.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 | // Nonnegative integers up to 9999. Returns 0 if either is zero. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, b) { if (a == 0 || b == 0) { return 0; } let x = a; let y = b; while (y != 0) { let r = x % y; x = y; y = r; } return (Math.floor(a / x)) * b; } |
Source
No original paper has been verified for this entry. This source is a reference text or teaching reference, not an asserted original publication.
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition)
Donald E. Knuth (1997). Reference book.