31
\$\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\$
  • 6
    \$\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\$ – Greg Martin Oct 1 '16 at 2:56

42 Answers 42

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\$
  • \$\begingroup\$ How would this work for testcases with more than 2 numbers as input? \$\endgroup\$ – JAD Dec 25 '16 at 13:32
  • \$\begingroup\$ @JarkoDubbeldam Thanks for pointing that out. Missed that part of the spec. \$\endgroup\$ – Billywob Dec 25 '16 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\$
0
\$\begingroup\$

J, 34 bytes

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

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

Try it online!

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

Scala, 44 bytes

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

Try it online!

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

Pyth, 7 bytes

f!s%LTQ

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.