# Least Common Multiple

The least common multiple of a set of positive integers A is the smallest postive integer B such that, for each k in A, there exists a positive integer n such that k*n = B.

Given at least two positive integers as input, output their least common multiple.

## Rules

• Builtins are allowed, but if your solution uses one, you are encouraged to include an alternate solution that does not use GCD/LCM builtins. However, the alternate solution will not count towards your score at all, so it is entirely optional.
• All inputs and outputs will be within the natively-representable range for your language. If your language is natively capable of arbitrarily-large integers, then your solution must work with arbitrarily large inputs and outputs.

## Test cases

[7, 2] -> 14
[8, 1] -> 8
[6, 4, 8] -> 24
[8, 2, 1, 10] -> 40
[9, 6, 2, 1, 5] -> 90
[5, 5, 7, 1, 1] -> 35
[4, 13, 8, 8, 11, 1] -> 1144
[7, 2, 2, 11, 11, 8, 5] -> 3080
[1, 6, 10, 3, 4, 10, 7] -> 420
[5, 2, 9, 10, 3, 4, 4, 4, 7] -> 1260
[9, 7, 10, 9, 7, 8, 5, 10, 1] -> 2520

• Because it's a reasonably frequent misconception: the formula LCM(a,b) = ab/GCD(a,b) does not extend to more than two numbers (or, for that matter, to one number!). Commented Oct 1, 2016 at 2:56

## JavaScript (ES6), 36 bytes

f=(a,i=1)=>a.some(v=>i%v)?f(a,i+1):i


Starting from 1 it's the first number that can be divided by all.

f=(a,i=1)=>a.some(v=>i%v)?f(a,i+1):i
;

console.log(f([7, 2]));
console.log(f([8, 1]));
console.log(f([6, 4, 8]));
console.log(f([8, 2, 1, 10]));
console.log(f([9, 6, 2, 1, 5]));
console.log(f([5, 5, 7, 1, 1]));
console.log(f([4, 13, 8, 8, 11, 1]));
console.log(f([7, 2, 2, 11, 11, 8, 5]));
console.log(f([1, 6, 10, 3, 4, 10, 7]));
console.log(f([5, 2, 9, 10, 3, 4, 4, 4, 7]));
console.log(f([9, 7, 10, 9, 7, 8, 5, 10, 1]));

• Of course... I thought about doing a loop with this technique, but recursion is way shorter. Commented Sep 30, 2016 at 19:26
• This is genius... If I recall, some returns true if at least one element in the array satisfies the condition, right? Commented Oct 4, 2016 at 2:49

# 05AB1E/2sable, 2 bytes

.¿


# Jelly, 3 bytes

æl/


Reduces by LCM. Try it online! or verify all test cases.

## Alternate version, 6 bytes

ÆE»/ÆẸ


### How it works

ÆE»/ÆẸ  Main link. Argument: A (array)

ÆE      Yield all prime exponents of each integer in A.
»/    Reduce columns (exponents that correspond to the same prime) by maximum.
ÆẸ  Turn the resulting array of prime exponents into the corresponding integer.


# Python, 696552 50 bytes

A=lambda l,i=1:any(i%a for a in l)and A(l,i+1)or i


2 bytes saved thanks to Dennis!

Pretty straightforward recursive solution, you will need to make the recursion limit a bit higher for some of the test cases to work.

• any takes a generator; you don't need the brackets. Commented Sep 30, 2016 at 19:10
• A=lambda l,i=1:all(i%a<1for a in l)or-~A(l,i+1) saves a few more bytes. Commented Sep 30, 2016 at 19:58

# MATL, 7 bytes

&YFX>^p


No builtin.

Try it online!

### Explanation

Let's take input [8, 2, 1, 10] as an example.

&YF    % Take array implicitly. Push vector of prime factors and matrix of exponents
% of factorization, where each row represents one of the input numbers
%   STACK: [2 3 5], [3 0 0; 1 0 0; 0 0 0; 1 0 1]
X>     % Maximum of each column
%   STACK: [2 3 5], [3 0 1]
^      % Element-wise power
%   STACK: [8 1 5]
p      % Product of array
%   STACK: 40
% Implicitly display


EDIT (June 9, 2017): YF with two outputs has been modified in release 20.1.0: non-factor primes and their (zero) exponents are skipped. This doesn't affect the above code, which works without requiring any changes.

# Julia (3 Bytes) [Working on Non-Built-in]

lcm     # Using LCM built-in (3 Bytes)


As Dennis pointed out, I keep forgetting that Julia automatically vectorizes inputs.

## Example:

println(lcm(1,2,3,4,5,6,7,8,9)) #Prints 2520


## PowerShell v2+, 73 60 bytes

param($a)for($i=1;($a|?{!($i%$_)}).count-ne$a.count){$i++}$i


Takes input $a, loops upward from $i=1 with $i++, based on a conditional. The condition is ($a|?{!($i%$_)}).count being -notequal to $a.count. Meaning, the loop ends when the elements of $a that are divisors of $i is equal to the elements of $a. Then, a solitary $i is left on the pipeline, and output is implicit. ### Test Cases PS C:\Tools\Scripts\golfing> @(7,2),@(8,1),@(6,4,8),@(8,2,1,10),@(9,6,2,1,5),@(5,5,7,1,1),@(4,13,8,8,11,1)|%{($_-join',')+" -> "+(.\least-common-multiple.ps1 $_)} 7,2 -> 14 8,1 -> 8 6,4,8 -> 24 8,2,1,10 -> 40 9,6,2,1,5 -> 90 5,5,7,1,1 -> 35 4,13,8,8,11,1 -> 1144 PS C:\Tools\Scripts\golfing> @(7,2,2,11,11,8,5),@(1,6,10,3,4,10,7),@(5,2,9,10,3,4,4,4,7),@(9,7,10,9,7,8,5,10,1)|%{($_-join',')+" -> "+(.\least-common-multiple.ps1 $_)} 7,2,2,11,11,8,5 -> 3080 1,6,10,3,4,10,7 -> 420 5,2,9,10,3,4,4,4,7 -> 1260 9,7,10,9,7,8,5,10,1 -> 2520  # Actually, 12 1 byte Golfing suggestions are still welcome, though I'm not sure how to improve on the raw LCM built-in. Try it online! ▲  A 12-byte version without the built-in. Golfing suggestions welcome. Try it online! ╗2╜@♀%ΣY╓N  Ungolfing  Implicit input array. ╗ Save array in register 0. 2...╓ Starting with f(0), find the first (two) x where f(x) returns a truthy value. These two values will be 0 and our LCM. ╜ Push array from register 0. @ Swap the top two values. Stack: x, array ♀% Map % over x and array, returning (x % item) for each item in array. ΣY If the sum of all the modulos equals 0, x is either 0 or our LCM. N Push the last (second) value of our results. This is our LCM. Implicit return.  • You do realize you're allowed to use the builtin, right? – user45941 Commented Oct 1, 2016 at 5:39 • @Mego I'll add it in, but my understanding was that builtins were discouraged, so I didn't use it at first. Commented Oct 1, 2016 at 6:16 • Builtins are allowed. They're not discouraged at all - I simply wanted to encourage non-builtin solutions to also be included because they are often much more interesting than the builtin. – user45941 Commented Oct 1, 2016 at 6:30 • I read that as actually, 1 byte. – user58826 Commented Apr 17, 2017 at 18:21 • @programmer5000 I think that may be why the language is called actually... Commented Sep 25, 2017 at 20:22 # Cheddar, 33 bytes (n,i=1)f->n.any(i&(%))?f(n,i+1):i  Nothing super new. ## Ungolfed (n, i = 1) f -> n.any(j -> i % j) ? f(n, i + 1) : i  Basically this starts at one and keeps increasing until it finds an LCM # JavaScript (ES6), 63 59 bytes f=([x,...a])=>a[0]?x*f(a)/(g=(m,n)=>n?g(n,m%n):m)(x,f(a)):x  Recursively finds the LCM of the last two elements. • This is what my solution would have been: a=>a.reduce((l,n)=>l*n/(g=(m,n)=>n?g(n,m%n):m)(l,n)) – Neil Commented Sep 30, 2016 at 19:15 • @Neil You can post that if you'd like. I doubt my technique can get that short... Commented Sep 30, 2016 at 19:32 # Mathematica, 3 bytes LCM  Usage: In[1]:= LCM[9, 7, 10, 9, 7, 8, 5, 10, 1] Out[1]= 2520  • The day that Mathematica matched Jelly is a day I never thought I'd see. Commented Oct 1, 2016 at 3:28 # Brachylog v2, 8 bytes {×↙Xℕ₁}ᵛ  Try it online! It's funny just how directly this maps on to the definition given in the challenge. { }ᵛ Each element of the input × multiplied by ↙X some arbitrary and inconsistent integer ℕ₁ is a natural number, ᵛ which is the same for each element, and is the output.  A suspiciously slow but significantly shorter solution: # Brachylog v2, 5 bytes f⊇p~d  Try it online! Takes input through the output variable and gives output through the input variable. Rips right through the first four test cases but I'm still waiting on the fifth... Ordinarily, I'd still make it my primary solution and just trust that it works correctly, but I don't know why it hasn't confirmed that 90 is the LCM of 9, 6, 2, 1, 5 when I gave it 90 twenty minutes ago. (Edit: It confirmed the answer after no more than 16 hours, and generated it alongside the LCM of 5, 5, 7, 1, 1 after about two days.)  The output variable ~d with duplicates removed p is a permutation of ⊇ a sublist of f the factors of the input variable.  And another completely different predicate that accidentally more-or-less translates Fatalize's Brachylog v1 solution: # Brachylog v2, 10 bytes ;.gᵗ↔z%ᵛ0<  Try it online! This was salvaged from a solution I'd made for this challenge before I realized the output wasn't restricted to being an integer.  . The output ; gᵗ↔z paired with each element of the input, %ᵛ when the first element of each pair is taken mod the second, is always 0 zero. Furthermore, the output < is strictly greater than 0 zero.  # Dyalog APL, 2 bytes ∧/  Reduces by LCM. Test it on TryAPL. • Congrats on 100k! Commented Sep 30, 2016 at 20:45 ## JavaScript (ES6), 52 bytes a=>a.reduce((l,n)=>l*n/(g=(m,n)=>n?g(n,m%n):m)(l,n))  I reduced this answer as much as I could but I'm obviously not going to get anywhere near the simplicity of @Hedi's answer. • a=>a.reduce(g=(x,y)=>x*=(x%=y)?g(y,x)/x:1); still longer than Hedi's – tsh Commented Apr 1, 2021 at 11:22 # Java 8, 7559121 89 bytes Uses the Euclidean Algorithm and the fact that LCM(A, B)= A * B / GCD(A, B) • 16 bytes off. Thanks to @carusocomputing • Added Multi-Input +62 bytes • 32 bytes off. Thanks to @Olivier Grégoire Code: public static int lcm(int l, int c){ for(int i=1;i<=l&&i<=c;++i) if (i%l==0&&i%c==0) return l*c/i; } public static int lcm(int...x){ int y=x[0]; for(int j:x){ y=lcm(j,y); } return y; }  Remove line-breaks: int g(int a,int b){return b<1?a:g(b,a%b);}  l->{int l=1;for(int n:a)l=l*n/g(l,n);return l;}  • Technically a snippet, but if you add n->{...} I believe it becomes valid Java 8. Commented Sep 30, 2016 at 20:27 • Thanks. I'm trying to get used to see lambda in Java. With lambda you can probably golf some of the for-loop. But I don't know how. Commented Sep 30, 2016 at 20:29 • Yeah, all that stuff is an afterthought in Java; you'd likely be better off learning it in Python :). Commented Sep 30, 2016 at 20:32 • Unless I'm missing something, this doesn't support more than two inputs Commented Oct 1, 2016 at 16:51 • If you compute the GCD, you can golf much more: int g(int a,int b){return b<1?a:g(b,a%b);}. LCM can then become int l(int[]a){int l=1;for(int n:a)l=l*n/g(l,n);return l;}, for a total of 99 bytes. Commented Oct 3, 2016 at 9:47 # MATL, 3 bytes &Zm  This uses the builtin function with array input. Try it online! # Brachylog, 17 bytes ,.#>=g:?z:%a#=h0,  Try it online! ### Explanation ,.#>= Output is a strictly positive integer g:?z Zip the Output with the Input :%a Compute Output mod I for each I in the Input #=h0, All results must be equal to 0  # C#, 50+18 = 68 bytes 50 bytes for method defintion, +18 bytes for LINQ import. using System.Linq;int L(int[]n,int i=1)=>n.All(x=>1>i%x)?i:L(n,i+1);  Pretty much the same as a lot of other answers. Counts up recursively until it finds the LCM. I was a bit surprised this didn't get a StackOverflowException, so I also have a non-recursive version which is actually just 1 byte longer. using System.Linq;n=>{for(int i=1;;i++)if(n.All(x=>1>i%x))return i;};  Ungolfed: using System.Linq; // Import LINQ int L(int[] n, int i = 1) => // Function declaration n.All(x => 1 > i % x) // Check if each x in n divides i ? i // And if so return i : L(n, i + 1) // Otherwise increment i and recurse ;  # Perl 6, 10 bytes {[lcm] @_}  basically the same as: sub ( *@_ ) { @_.reduce: &infix:< lcm > }  # J, 11 bytes >./&.(_&q:)  There is a solution for 3 bytes using the LCM builtin. *./  ## Explanation >./&.(_&q:) Input: array of integers A _&q: Get the prime exponents of each integer in A >./& Reduce by maximum on the lists &. _&q: Convert the list of exponents back to an integer *./ Input: array of integers A / Reduce using *. LCM  # CJam, 1817 16 bytes 1 byte saved thanks to Martin Ender. Incrementing until the LCM is found. q~0{)_2$f%:+}g\;


Try it online

• I'm not entirely familiar with CJam, but the reusability rule is for functions, not full programs. If your 17-byte solution is a full program that consistently works across runs, it's fine.
– user45941
Commented Oct 2, 2016 at 17:31

## Racket 13 bytes

lcm is a built-in function in Racket:

(apply lcm l)


Testing:

(define (f l)
(apply lcm l))

(f (list 7 2))
(f (list 8 1))
(f (list 6 4 8))
(f (list 8 2 1 10))
(f (list 9 6 2 1 5))
(f (list 5 5 7 1 1))
(f (list 4 13 8 8 11 1))
(f (list 7 2 2 11 11 8 5))
(f (list 1 6 10 3 4 10 7))
(f (list 5 2 9 10 3 4 4 4 7))
(f (list 9 7 10 9 7 8 5 10 1))


Output:

14
8
24
40
90
35
1144
3080
420
1260
2520

• Ahh. How can you use that syntax. I always gave up when I tried to learn Racket. Commented Oct 1, 2016 at 17:22
• First word in brackets is a procedure name, rest are its arguments. If an argument is a procedure, it has to be in its own brackets. Values (non-procedures) are written without brackets. I find it to be an excellent general-purpose language with additional advantage of stress on functional programming. Being derived from Lisp, one also gets a sense of covering that area of programming.
– rnso
Commented Oct 1, 2016 at 18:19
• I find coding keywords and language to be easier in Racket & Scheme than Lisp.
– rnso
Commented Oct 1, 2016 at 18:26
• Yes, but did I said I understand Lisp? I more like languages like Jelly or Java. Commented Oct 1, 2016 at 18:27
• Main syntax difference between Java and Racket is f(a, b) vs (f a b), x+y+z vs (+ x y z), x == y vs (eq? x y) and x=2 vs (define x 2), or if already defined, (set! x 2). Also no need to declare types like public static void or int char string etc. Hope that gets you interested in Racket again.
– rnso
Commented Oct 2, 2016 at 3:53

# R, 36 bytes (not builtin)

v=scan();i=1;while(any(i%%v))i=i+1;i


Takes the input. Then tests each positive integer by taking the mod.

• I believe you need a cat around your last i Commented Oct 13, 2017 at 20:10
• @Giuseppe when I run it, the value prints fine. Commented Oct 13, 2017 at 20:19
• see the discussion here, but I suppose ec=T is fine for +4 rather than +5 for cat(). Commented Oct 13, 2017 at 20:22
• regardless, this can be golfed down some v=scan();while(any((F=F+1)%%v)){};F with cat() or ec=T making it 40 or 39 bytes, respectively. And +1, very nice approach. Commented Oct 13, 2017 at 20:23

# APOL, 49 bytes

v(0 1);v(1 i);w(⊕(ƒ(s(¹) %(⁰ I(∋)))) ∆(0));-(⁰ 1)

This could almost certaintly be made shorter, maybe I'll come back to it later.

# Pyth, 9 bytes

.U/*bZibZ


A program that takes input of a list on STDIN and prints the result.

How it works

.U/*bZibZ  Program. Input: Q
.U         Reduce Q by (implicit input fill):
*bZ      Product of current and next value
/   ibZ   divided by GCD of current and next value
Implicitly print


foldr1 lcm


Usage example: foldl1 lcm [5,2,9,10,3,4,4,4,7] -> 1260.

## Pip, 10 bytes

W$+o%g++oo  Uses the "try every number until one works" strategy. Try it online!  o is preinitialized to 1, g is list of cmdline args o%g Mod o by each arg$+         Sum (truthy if any nonzero, falsy if all zero)
W           Loop while that expression is truthy:
++o     Increment o
o  Autoprint o


## PHP, 42 74 bytes

for(;($p=++$f*$argv[1])%$argv[2];);echo$p;  straight forward: loop $f from 1 upwards; if $f*$a divides through $b without a remainder, the LCM is found. I totally had overread the at least ... here´s the code for any number of parameters: for(;$i<$argc;)for($p=$argv[$i=1]*++$f;++$i<$argc&$p%$argv[$i]<1;);echo$p;  Loop $f from 1 upwards while inner loop has not run to $argc. Loop $i from 2 to $argc-1 while $f*$argv[1] divides through $argv[$i] without a remainder. both loops broken: print $f*\$argument 1.

# Prolog (SWI), 46 bytes

l([],1).
l([X|Y],P):-l(Y,Q),P is X*Q/gcd(X,Q).


Try it online!

Another solution, 59 bytes:

l(A,X):-between(1,inf,X),forall(member(Y,A),X mod Y=:=0),!.


# J, 34 bytes

*/@((0 1+])^:(*@+/@:|*/)^:_>./,1:)


A while loop iterating through multiples of the largest number in input.

Try it online!