36
\$\begingroup\$

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
\$\endgroup\$
1
  • 8
    \$\begingroup\$ 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!). \$\endgroup\$ Commented Oct 1, 2016 at 2:56

49 Answers 49

1
2
1
\$\begingroup\$

Scala, 44 bytes

Stream.from(1).find(i=>x.forall(i%_==0)).get

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 83 bytes

import math,functools as i
t=lambda t:i.reduce(lambda a,b:int(a*b/math.gcd(a,b)),t)
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$
    – Laikoni
    Commented Jul 10, 2018 at 17:36
  • \$\begingroup\$ You may want to include a link to an online testing site like Try it online! so it's easier for others to verify your answer. \$\endgroup\$
    – Laikoni
    Commented Jul 10, 2018 at 17:40
1
\$\begingroup\$

Pyth, 7 bytes

f!s%LTQ

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3.9, 20 bytes

import math
math.lcm

Now Python 3.9 has a builtin in math module to calculate LCM of two or more integers.

\$\endgroup\$
1
\$\begingroup\$

Rust, 45 bytes

|i:&[_]|(1..).find(|v|i.iter().all(|a|v%a<1))

Try it online!

Iterates over all numbers until finding the first one which is divisible by all the numbers in the given slice. Hey, it saves bytes!

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 2 bytes

∆Ŀ

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 17 bytes

->x{x.inject:lcm}

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 3 bytes

lcm

Without builtins, 50 bytes:

v->fold((a,b)->for(k=a,a*b,k%b||k%a||return(k)),v)

The forstep version is 1 byte longer. Older versions can shave 2 bytes with | in place of ||.

\$\endgroup\$
1
\$\begingroup\$

Thunno 2, 1 byte

ŀ

Try it online!

Non built-in,  6 5  4 bytes:

ƘŒS~

Try it online!

-1 thanks to @Jacob

Explanation

ŀ  # Implicit input. Built-in to calculate LCM. Implicit output.

ƘŒS~  # Implicit input
Ƙ     # Find the first positive integer where:
 Π   #  The number mod the input (vectorises)
  S~  #  Has a sum of 0 (i.e. it contains only zeros)
      # Implicit output
\$\endgroup\$
2
  • \$\begingroup\$ Replace $% with Œ for -1 \$\endgroup\$ Commented Apr 23, 2023 at 16:35
  • \$\begingroup\$ @Jacob oh, I got what you're saying now. Yes, that would work because inputs are reusable in Thunno 2. Thanks! \$\endgroup\$
    – The Thonnu
    Commented Apr 23, 2023 at 16:37
0
\$\begingroup\$

Pyth - 7 6 bytes

No builtin.

*F{sPM

Try it online here.

\$\endgroup\$
1
  • 5
    \$\begingroup\$ Fails on [4], or anything else with a repeated prime factor. \$\endgroup\$
    – isaacg
    Commented Sep 30, 2016 at 20:08
0
\$\begingroup\$

Java 7, 75 bytes

int f(int[]a){int i=1,s=1;for(;s>0;i++){s=0;for(int b:a)s+=i%b;}return--i;}

A simple two-loop method. Start at one and check to see when all the remainders add to zero.

I had to jump through some dumb hoops with s. There's probably a better way to do that, but it's 1:00 AM and it'll have to wait :/

\$\endgroup\$
0
\$\begingroup\$

R, 30 21 bytes

Using the mLCM function from the numbers package:

numbers::mLCM(scan())

Or without builtins (81 bytes):

L=function(x,y,g=function(x,y,r=x%%y)`if`(r,g(y,r),y))x*y/g(x,y)
Reduce(L,scan())

We first define a function L for the pair-wise LCM and then apply it iteratively using Reduce.

\$\endgroup\$
2
  • \$\begingroup\$ How would this work for testcases with more than 2 numbers as input? \$\endgroup\$
    – JAD
    Commented Dec 25, 2016 at 13:32
  • \$\begingroup\$ @JarkoDubbeldam Thanks for pointing that out. Missed that part of the spec. \$\endgroup\$
    – Billywob
    Commented Dec 25, 2016 at 14:23
0
\$\begingroup\$

PHP, 65 Bytes

<?for($t=1;$t&&++$i;$t=!$t)foreach($_GET as$v)$t*=$i%$v<1;echo$i;

Try it online!

or

for(;++$i;!$t?:die("$i"))for($n=$t=1;$v=$argv[$n++];)$t*=$i%$v<1;

or

<?for($t=1;++$i;$t=!$t?:die("$i"))foreach($_GET as$v)$t*=$i%$v<1;

PHP, 96 Bytes

with 2 loops

while(1<count($a=&$_GET[i])){$e=array_pop($a);for($i=0;($m=++$i*$e)%$a[0];);$a[0]=$m;}echo$a[0];

based on set theory 128 Bytes

$p=array_product($a=$_GET[i]);echo min(array_intersect(...array_map($r=function($n)use($p){return range($n,$p,$n);},$_GET[i])));
\$\endgroup\$
0
\$\begingroup\$

Axiom, 19 bytes

f(x)==reduce(lcm,x)

Could be perhaps better and right but longer

f(x:List PI):PI==reduce(lcm,x)
\$\endgroup\$
0
\$\begingroup\$

J, 27 bytes

not using built ins, naive solution

>:0 i.~+/"1 i|"1 0>:i.*/i=.

usage

>:0 i.~+/"1 i|"1 0>:i.*/i=.9 6 2 1 5

returns 90

\$\endgroup\$
0
\$\begingroup\$

Japt, 8 bytes

@e!vX}a1

Try it

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 52 + 2 (-pa) = 54 bytes

$r=$\=$_;while($r){$r=0;$r||=$\%$_ for@F;$r&&$\++}}{

Try it online!

\$\endgroup\$
0
\$\begingroup\$

A little late to the party, but I didn't see an AWK answer.

AWK, 49 bytes

{for(x=1;x&&++m;)for(x=i=0;i++<NF;)x+=m%$i;$0=m}1

Try it online!

NOTE: The link has 2 extra bytes m= in front of the x=1;x... to simplify testing/allow multiple inputs/outputs. However, the m= fails for single/repeated input value of 1. The code as written handles 1 fine.

\$\endgroup\$
0
\$\begingroup\$

Jq 1.5, 67 bytes

Not very smart. Just tests each i from 2 to product of numbers.

first(range(2;1+reduce.[]as$x(1;.*$x))as$i|select(all($i%.==0))|$i)

More efficient but longer:

def g(a;b):if b<1then a else g(b;a%b)end;reduce.[]as$x(1;.*$x/g(.;$x))

Try it online!

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.