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

1
2
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 :/

| improve this answer | |
\$\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.

| improve this answer | |
\$\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])));
| improve this answer | |
\$\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)
| improve this answer | |
\$\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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Japt, 8 bytes

@e!vX}a1

Try it

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

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

Try it online!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

J, 34 bytes

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

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Scala, 44 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Pyth, 7 bytes

f!s%LTQ

Try it online!

| improve this answer | |
\$\endgroup\$
1
2

Your Answer

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