Najmniejsza wspólna wielokrotność

31

Najmniejszą wielokrotnością zbioru dodatnich liczb całkowitych Ajest najmniejsza liczba całkowita dodatnia, Btaka, że ​​dla każdego kz Anich istnieje dodatnia liczba całkowita ntaka, że k*n = B.

Biorąc pod uwagę co najmniej dwie dodatnie liczby całkowite jako dane wejściowe, wypisz ich najmniejszą wspólną wielokrotność.

Zasady

  • Wbudowane są dozwolone, ale jeśli twoje rozwiązanie korzysta z jednego, zachęcamy do dołączenia alternatywnego rozwiązania, które nie korzysta z wbudowanych GCD / LCM. Jednak alternatywne rozwiązanie w ogóle nie będzie wliczane do wyniku, więc jest całkowicie opcjonalne.
  • Wszystkie dane wejściowe i wyjściowe będą się mieścić w natywnie reprezentatywnym zakresie dla twojego języka. Jeśli twój język ma natywną zdolność do dowolnie dużych liczb całkowitych, wtedy twoje rozwiązanie musi działać z dowolnie dużymi wejściami i wyjściami.

Przypadki testowe

[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
Mego
źródło
6
Ponieważ jest to dość częste nieporozumienie: wzór LCM (a, b) = ab / GCD (a, b) nie rozciąga się na więcej niż dwie liczby (lub, w tym przypadku, na jedną liczbę!).
Greg Martin

Odpowiedzi:

4

Właściwie 12 1 bajt

Sugestie dotyczące gry w golfa są nadal mile widziane, chociaż nie jestem pewien, jak ulepszyć wbudowane surowe LCM. Wypróbuj online!

Wersja 12-bajtowa bez wbudowanego. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj 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.
Sherlock9
źródło
Zdajesz sobie sprawę, że możesz używać wbudowanego, prawda?
Mego
1
@Mego Dodam to, ale rozumiem, że wbudowane wersje były zniechęcone, więc nie użyłem go na początku.
Sherlock9
1
Wbudowane są dozwolone. W ogóle ich nie zniechęcają - po prostu chciałem zachęcić do włączenia niewbudowanych rozwiązań, ponieważ są one często znacznie ciekawsze niż wbudowane.
Mego
1
Przeczytałem to jako 1 bajt .
programator5000
2
@ programmer5000 Myślę, że może dlatego tak nazywa się ten język ...
Socratic Phoenix
17

JavaScript (ES6), 36 bajtów

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

Począwszy od 1pierwszej liczby, którą można podzielić przez wszystkich.

Hedi
źródło
Oczywiście ... Myślałem o zrobieniu pętli z tą techniką, ale rekursja jest znacznie krótsza.
ETHproductions
1
To jest genialne ... Jeśli pamiętam, somezwraca true, jeśli przynajmniej jeden element w tablicy spełnia warunek, prawda?
WallyWest,
11

Galaretka , 3 bajty

æl/

Zmniejsza o LCM. Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Alternatywna wersja, 6 bajtów

ÆE»/ÆẸ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Æ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.
Dennis
źródło
8

Python, 69 65 52 50 bajtów

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

2 bajty zapisane dzięki Dennisowi!

Dość proste rozwiązanie rekurencyjne, aby niektóre przypadki testowe działały, należy nieco zwiększyć limit rekurencji.

Loovjo
źródło
1
anybierze generator; nie potrzebujesz nawiasów.
Dennis
3
A=lambda l,i=1:all(i%a<1for a in l)or-~A(l,i+1)oszczędza jeszcze kilka bajtów.
Dennis
8

MATL , 7 bajtów

&YFX>^p

Brak wbudowanego.

Wypróbuj online!

Wyjaśnienie

Weźmy [8, 2, 1, 10]za przykład przykład.

&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

EDYCJA (9 czerwca 2017 r.): YFDwie wersje zostały zmodyfikowane w wersji 20.1.0 : liczby pierwsze nieczynnikowe i ich (zero) wykładniki są pomijane. Nie wpływa to na powyższy kod, który działa bez żadnych zmian.

Luis Mendo
źródło
6

Julia (3 bajty) [Praca nad niewbudowanym]

lcm     # Using LCM built-in (3 Bytes)

Jak zauważył Dennis, zapominam, że Julia automatycznie wektoryzuje dane wejściowe.

Przykład:

println(lcm(1,2,3,4,5,6,7,8,9)) #Prints 2520
Urna Magicznej Ośmiornicy
źródło
6

PowerShell v2 +, 73 60 bajtów

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

Pobiera dane wejściowe $a, zapętla w górę od $i=1z $i++, na podstawie warunkowej. Warunkiem jest ($a|?{!($i%$_)}).countbycie -not equal do $a.count. Oznacza to, że pętla kończy się, gdy elementy, $aktóre dzielnikami, $isą równe elementom $a. Następnie $iw rurociągu pozostaje samotnik , a wynik jest domyślny.

Przypadki testowe

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
AdmBorkBork
źródło
4

Mathematica, 3 bajty

LCM

Stosowanie:

In[1]:= LCM[9, 7, 10, 9, 7, 8, 5, 10, 1]                                        

Out[1]= 2520
alephalpha
źródło
6
Dzień, w którym Mathematica dopasowała galaretkę, to dzień, o którym nigdy nie myślałem, że go zobaczę.
Steven H.
3

Cheddar, 33 bajty

(n,i=1)f->n.any(i&(%))?f(n,i+1):i

Nic super nowego.

Bez golfa

(n, i = 1) f ->
  n.any(j -> i % j) ?
    f(n, i + 1) :
    i

Zasadniczo zaczyna się od jednego i rośnie, aż znajdzie LCM

Downgoat
źródło
3

JavaScript (ES6), 63 59 bajtów

f=([x,...a])=>a[0]?x*f(a)/(g=(m,n)=>n?g(n,m%n):m)(x,f(a)):x

Rekurencyjnie znajduje LCM dwóch ostatnich elementów.

ETHprodukcje
źródło
Takie byłoby moje rozwiązanie:a=>a.reduce((l,n)=>l*n/(g=(m,n)=>n?g(n,m%n):m)(l,n))
Neil
@Neil Możesz to opublikować, jeśli chcesz. Wątpię, czy moja technika może być tak krótka ...
ETHproductions
3

Dyalog APL, 2 bajty

∧/

Zmniejsza o LCM. Przetestuj na TryAPL .

Dennis
źródło
4
Gratulacje na 100 000!
Copper
3

JavaScript (ES6), 52 bajty

a=>a.reduce((l,n)=>l*n/(g=(m,n)=>n?g(n,m%n):m)(l,n))

I reducebyłyby to odpowiedź tyle, ile mogłem, ale ja oczywiście nie zamierza zbliżyć prostocie @ odpowiedź Hedi za.

Neil
źródło
3

Java 8, 75 59 121 89 bajtów

Wykorzystuje algorytm euklidesowy oraz fakt, że LCM (A, B) = A * B / GCD (A, B)

  • 16 bajtów wyłączone. Dzięki @carusocomputing
  • Dodano Multi-Input + 62 bajty
  • 32 bajty wyłączone. Dzięki @Olivier Grégoire

Kod:

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;
}

Usuń podział linii:

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;}
Roman Gräf
źródło
Technicznie rzecz biorąc, fragment, ale jeśli dodasz, n->{...}uważam, że staje się ważny Java 8.
Magic Octopus Urn
Dzięki. Próbuję przyzwyczaić się do zobaczenia lambda w Javie. Z lambda możesz prawdopodobnie zagrać w golfa w części for-loop. Ale nie wiem jak.
Roman Gräf
Tak, wszystkie te rzeczy są późniejszą refleksją w Javie; prawdopodobnie lepiej byłoby uczyć się go w Pythonie :).
Magic Octopus Urn
Chyba że coś mi brakuje, nie obsługuje to więcej niż dwóch danych wejściowych
pinkfloydx33
Jeśli obliczenia GCD, można golf wiele więcej: int g(int a,int b){return b<1?a:g(b,a%b);}. LCM może wtedy zostać int l(int[]a){int l=1;for(int n:a)l=l*n/g(l,n);return l;}w sumie 99 bajtów.
Olivier Grégoire
2

Brachylog , 17 bajtów

,.#>=g:?z:%a#=h0,

Wypróbuj online!

Wyjaśnienie

,.#>=               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
Fatalizować
źródło
2

Perl 6 , 10 bajtów

{[lcm] @_}

w zasadzie taki sam jak:

sub ( *@_ ) { @_.reduce: &infix:< lcm > }
Brad Gilbert b2gills
źródło
2

J, 11 bajtów

>./&.(_&q:)

Istnieje rozwiązanie dla 3 bajtów przy użyciu wbudowanego LCM.

*./

Wyjaśnienie

>./&.(_&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
mile
źródło
2

CJam, 18 17 16 bajtów

1 bajt zapisany dzięki Martinowi Enderowi.

Zwiększanie aż do znalezienia LCM.

q~0{)_2$f%:+}g\;

Wypróbuj online

Neorej
źródło
1
CJam nie jestem do końca zaznajomiony, ale reguła wielokrotnego użytku dotyczy funkcji, a nie pełnych programów. Jeśli twoje 17-bajtowe rozwiązanie jest pełnym programem, który konsekwentnie działa w różnych uruchomieniach, jest w porządku.
Mego
2

Rakieta 13 bajtów

lcm to wbudowana funkcja w Racket:

(apply lcm l)

Testowanie:

(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))

Wydajność:

14
8
24
40
90
35
1144
3080
420
1260
2520
rnso
źródło
Ahh Jak możesz użyć tej składni. Zawsze się poddawałem, kiedy próbowałem nauczyć się Rakiety.
Roman Gräf
1
Pierwsze słowo w nawiasach to nazwa procedury, reszta to jej argumenty. Jeśli argument jest procedurą, musi znajdować się w nawiasach. Wartości (nieprocesowe) są zapisywane bez nawiasów. Uważam, że jest to doskonały język ogólnego zastosowania z dodatkową zaletą nacisku na programowanie funkcjonalne. Pochodząc z Lisp, można również poczuć, że obejmuje ten obszar programowania.
rnso
Uważam, że kodowanie słów kluczowych i języka jest łatwiejsze w Racket & Scheme niż Lisp.
rnso
Tak, ale czy powiedziałem, że rozumiem Lisp? Bardziej lubię języki takie jak Jelly lub Java.
Roman Gräf
1
Główna różnica w składni między Javą a Racketem to f (a, b) vs (fab), x + y + z vs (+ xyz), x == y vs (eq? Xy) i x = 2 vs (zdefiniuj x 2) lub, jeśli już zdefiniowano, (ustaw! x 2). Nie trzeba też deklarować typów takich jak public static void lub int char string itp. Mam nadzieję, że ponownie zainteresuje Cię rakieta.
rnso
2

R, 36 bajtów (nie wbudowane)

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

Pobiera dane wejściowe. Następnie przetestuj każdą dodatnią liczbę całkowitą, biorąc mod.

użytkownik5957401
źródło
Sądzę, że potrzebujesz catswojego ostatniegoi
Giuseppe,
@Giuseppe, kiedy go uruchamiam, wartość drukuje się dobrze.
user5957401
zobacz dyskusję tutaj , ale przypuszczam, że ec=Tjest w porządku dla +4 zamiast +5 dla cat().
Giuseppe,
1
Niezależnie od tego, to można golfed dół niektóre v=scan();while(any((F=F+1)%%v)){};Fz cat()lub ec=Tczyni on 40 lub 39 bajtów, odpowiednio. I +1, bardzo fajne podejście.
Giuseppe,
1

Pyth, 9 bajtów

.U/*bZibZ

Program, który pobiera dane z listy na STDIN i drukuje wynik.

Wypróbuj online lub sprawdź wszystkie przypadki testowe

Jak to działa

.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
TheBikingViking
źródło
1

Haskell, 10 bajtów

foldr1 lcm

Przykład użycia: foldl1 lcm [5,2,9,10,3,4,4,4,7]-> 1260.

nimi
źródło
1

C #, 50 + 18 = 68 bajtów

50 bajtów na definicję metody, +18 bajtów na import LINQ.

using System.Linq;int L(int[]n,int i=1)=>n.All(x=>1>i%x)?i:L(n,i+1);

Prawie tak samo jak wiele innych odpowiedzi. Zlicza rekurencyjnie, aż znajdzie LCM. Byłem trochę zaskoczony, że nie dostałem wyjątku StackOverflowException, więc mam także wersję nierekurencyjną, która jest w rzeczywistości tylko 1 bajt dłużej.

using System.Linq;n=>{for(int i=1;;i++)if(n.All(x=>1>i%x))return i;};

Nie golfowany:

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
;
mleko
źródło
1

Pip , 10 bajtów

W$+o%g++oo

Wykorzystuje strategię „wypróbuj każdą liczbę, aż zadziała”. Wypróbuj 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
DLosc
źródło
1

PHP, 42 74 bajty

for(;($p=++$f*$argv[1])%$argv[2];);echo$p;

prosto:
pętla $fod 1 w górę; jeśli $f*$adzieli się $bbez reszty, LCM zostaje znalezione.


Całkowicie przeczytałem at least... oto kod dla dowolnej liczby parametrów:

for(;$i<$argc;)for($p=$argv[$i=1]*++$f;++$i<$argc&$p%$argv[$i]<1;);echo$p;

Pętla $fod 1 w górę, podczas gdy pętla wewnętrzna nie uruchomiła się do $ argc.
Pętla $iod 2do $argc-1podczas gdy $f*$argv[1]dzieli się $argv[$i]bez reszty.
obie pętle zepsute: drukuj $f*$argument 1.

Tytus
źródło
1

Prolog (SWI) , 46 bajtów

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

Wypróbuj online!

Inne rozwiązanie, 59 bajtów:

l(A,X):-between(1,inf,X),forall(member(Y,A),X mod Y=:=0),!.
eush77
źródło
1

Python 3, 83 bajty

import math,functools as i
t=lambda t:i.reduce(lambda a,b:int(a*b/math.gcd(a,b)),t)
Hydreigos
źródło
Witamy w PPCG!
Laikoni,
Możesz dołączyć link do strony testowej online, takiej jak Wypróbuj online! więc inni mogą łatwiej zweryfikować twoją odpowiedź.
Laikoni,
1

Brachylog v2, 8 bajtów

{×↙Xℕ₁}ᵛ

Wypróbuj online!

To zabawne, jak bezpośrednio przekłada się to na definicję podaną w wyzwaniu.

{     }ᵛ    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.

Podejrzanie powolne, ale znacznie krótsze rozwiązanie:

Brachylog v2, 5 bajtów

f⊇p~d

Wypróbuj online!

Pobiera dane wejściowe przez zmienną wyjściową i podaje dane wyjściowe przez zmienną wejściową. Przeszukuje pierwsze cztery przypadki testowe, ale wciąż czekam na piąte ... Zwykle nadal robiłbym to moje podstawowe rozwiązanie i po prostu wierzę, że działa poprawnie, ale nie wiem, dlaczego nie potwierdził, że 90 to LCM, 9, 6, 2, 1, 5kiedy dałem go 90 dwadzieścia minut temu.

(Edycja: potwierdziła odpowiedź po nie więcej niż 16 godzinach i wygenerowała ją obok LCM 5, 5, 7, 1, 1po około dwóch dniach).

         The output variable
   ~d    with duplicates removed
  p      is a permutation of
 ⊇       a sublist of
f        the factors of
         the input variable.

I inny zupełnie inny predykat, który przypadkowo mniej więcej tłumaczy rozwiązanie Brachylog v1 firmy Fatalize:

Brachylog v2, 10 bajtów

;.gᵗ↔z%ᵛ0<

Wypróbuj online!

To zostało uratowane z rozwiązania, dla którego stworzyłem tego wyzwania, zanim zdałem sobie sprawę, że wyjście nie jest ograniczone do liczby całkowitej.

 .            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.
Niepowiązany ciąg
źródło
0

Pyth - 7 6 bajtów

Brak wbudowanego.

*F{sPM

Wypróbuj online tutaj .

Maltysen
źródło
4
Nie [4]działa lub cokolwiek innego z powtarzającym się czynnikiem podstawowym.
isaacg