Kelipatan persekutuan terkecil

31

Paling umum beberapa dari himpunan bilangan bulat positif Aterkecil postive bilangan bulat Bseperti itu, untuk setiap kdi A, terdapat bilangan bulat positif nsehingga k*n = B.

Diberikan setidaknya dua bilangan bulat positif sebagai input, menghasilkan kelipatan paling tidak umum mereka.

Aturan

  • Builtin diperbolehkan, tetapi jika solusi Anda menggunakannya, Anda disarankan untuk memasukkan solusi alternatif yang tidak menggunakan builtin GCD / LCM. Namun, solusi alternatif tidak akan dihitung sama sekali dengan skor Anda, sehingga sepenuhnya opsional.
  • Semua input dan output akan berada dalam kisaran yang secara representatif dapat mewakili bahasa Anda. Jika bahasa Anda secara bawaan mampu menghasilkan bilangan bulat besar secara sewenang-wenang, maka solusi Anda harus bekerja dengan input dan output yang besar dan sewenang-wenang.

Uji kasus

[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
sumber
6
Karena itu adalah kesalahpahaman yang cukup sering: rumus LCM (a, b) = ab / GCD (a, b) tidak meluas ke lebih dari dua angka (atau, dalam hal ini, ke satu angka!).
Greg Martin

Jawaban:

4

Sebenarnya, 12 1 byte

Saran golf masih diterima, meskipun saya tidak yakin bagaimana meningkatkan pada built-in LCM mentah. Cobalah online!

Versi 12 byte tanpa built-in. Saran golf diterima. Cobalah online!

╗2`╜@♀%ΣY`╓N

Tidak melakukanolf

          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
sumber
Anda sadar bahwa Anda diperbolehkan menggunakan builtin, bukan?
Mego
1
@Mego saya akan menambahkannya, tetapi pemahaman saya adalah bahwa builtin tidak disarankan, jadi saya tidak menggunakannya pada awalnya.
Sherlock9
1
Dibangun secara bawaan. Mereka tidak berkecil hati sama sekali - saya hanya ingin mendorong solusi non-builtin untuk dimasukkan juga karena mereka sering jauh lebih menarik daripada builtin.
Mego
1
Saya membaca bahwa sebenarnya, 1 byte .
programmer5000
2
@ programmer5000 Saya pikir itu mungkin mengapa bahasa ini disebut sebenarnya ...
Socratic Phoenix
17

JavaScript (ES6), 36 byte

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

Mulai dari 1itu angka pertama yang bisa dibagi oleh semua.

Hedi
sumber
Tentu saja ... Saya berpikir tentang melakukan loop dengan teknik ini, tetapi rekursi jauh lebih pendek.
ETHproduksi
1
Ini jenius ... Jika saya ingat, somemengembalikan true jika setidaknya satu elemen dalam array memenuhi syarat, kan?
WallyWest
11

Jelly , 3 byte

æl/

Dikurangi oleh LCM. Cobalah online! atau verifikasi semua kasus uji .

Versi alternatif, 6 byte

ÆE»/ÆẸ

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Æ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
sumber
8

Python, 69 65 52 50 byte

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

2 byte disimpan berkat Dennis!

Solusi rekursif yang cukup mudah, Anda harus membuat batas rekursi sedikit lebih tinggi untuk beberapa kasus uji untuk bekerja.

Loovjo
sumber
1
anymengambil generator; Anda tidak membutuhkan tanda kurung.
Dennis
3
A=lambda l,i=1:all(i%a<1for a in l)or-~A(l,i+1)menghemat beberapa byte lagi.
Dennis
8

MATL , 7 byte

&YFX>^p

Tidak ada builtin

Cobalah online!

Penjelasan

Mari kita ambil input [8, 2, 1, 10]sebagai contoh.

&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 (9 Juni 2017): YFdengan dua output telah dimodifikasi dalam rilis 20.1.0 : bilangan prima non-faktor dan eksponen (nol) dilewati. Ini tidak memengaruhi kode di atas, yang berfungsi tanpa memerlukan perubahan apa pun.

Luis Mendo
sumber
6

Julia (3 Bytes) [Bekerja pada Non-Built-in]

lcm     # Using LCM built-in (3 Bytes)

Seperti yang ditunjukkan Dennis, saya selalu lupa bahwa Julia secara otomatis membuat vektor input.

Contoh:

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

PowerShell v2 +, 73 60 byte

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

Mengambil input $a, loop ke atas dari $i=1dengan $i++, berdasarkan pada kondisi. Kondisi ini ($a|?{!($i%$_)}).countmenjadi -not equal untuk $a.count. Artinya, loop berakhir ketika elemen $ayang merupakan pembagi $isama dengan elemen $a. Kemudian, soliter $idibiarkan dalam pipa, dan output tersirat.

Uji Kasus

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
sumber
4

Mathematica, 3 byte

LCM

Pemakaian:

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

Out[1]= 2520
alephalpha
sumber
6
Hari yang cocok dengan Mathematica Jelly adalah hari yang tidak pernah terpikir olehku untuk melihatnya.
Steven H.
3

Cheddar, 33 byte

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

Tidak ada yang super baru.

Tidak disatukan

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

Pada dasarnya ini dimulai pada satu dan terus meningkat sampai menemukan LCM

Downgoat
sumber
3

JavaScript (ES6), 63 59 byte

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

Secara rekursif menemukan LCM dari dua elemen terakhir.

Produksi ETH
sumber
Inilah yang akan menjadi solusi saya:a=>a.reduce((l,n)=>l*n/(g=(m,n)=>n?g(n,m%n):m)(l,n))
Neil
@Neil Anda dapat memposting itu jika Anda mau. Saya ragu teknik saya bisa sesingkat itu ...
ETHproduksi
3

Dyalog APL, 2 byte

∧/

Dikurangi oleh LCM. Uji di TryAPL .

Dennis
sumber
4
Selamat 100k!
Tembaga
3

JavaScript (ES6), 52 byte

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

Saya reducemenjawab ini semampu saya, tetapi saya jelas tidak akan mendekati kesederhanaan jawaban @Hedi.

Neil
sumber
3

Java 8, 75 59 121 89 byte

Menggunakan Algoritma Euclidean dan fakta bahwa LCM (A, B) = A * B / GCD (A, B)

  • Off 16 byte. Berkat @carusocomputing
  • Menambahkan Multi-Input + 62 byte
  • Off 32 byte. Terima kasih kepada @Olivier Grégoire

Kode:

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

Hapus jeda baris:

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
sumber
Secara teknis cuplikan, tetapi jika Anda menambahkan n->{...}saya percaya itu menjadi Java 8 yang benar.
Magic Gurita Guci
Terima kasih. Saya mencoba membiasakan diri melihat lambda di Jawa. Dengan lambda Anda mungkin bisa bermain golf untuk beberapa loop. Tapi saya tidak tahu caranya.
Roman Gräf
Ya, semua itu adalah renungan di Jawa; Anda mungkin akan lebih baik mempelajarinya dengan Python :).
Magic Gurita Guci
Kecuali saya kehilangan sesuatu, ini tidak mendukung lebih dari dua input
pinkfloydx33
Jika Anda menghitung GCD, Anda dapat golf lebih: int g(int a,int b){return b<1?a:g(b,a%b);}. LCM kemudian bisa menjadi int l(int[]a){int l=1;for(int n:a)l=l*n/g(l,n);return l;}, dengan total 99 byte.
Olivier Grégoire
2

Brachylog , 17 byte

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

Cobalah online!

Penjelasan

,.#>=               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
Fatalisasi
sumber
2

Perl 6 , 10 byte

{[lcm] @_}

pada dasarnya sama dengan:

sub ( *@_ ) { @_.reduce: &infix:< lcm > }
Brad Gilbert b2gills
sumber
2

J, 11 byte

>./&.(_&q:)

Ada solusi untuk 3 byte menggunakan LCM builtin.

*./

Penjelasan

>./&.(_&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
mil
sumber
2

CJam, 18 17 16 byte

1 byte disimpan berkat Martin Ender.

Bertambah sampai LCM ditemukan.

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

Cobalah online

Neorej
sumber
1
Saya tidak sepenuhnya akrab dengan CJam, tetapi aturan reusability adalah untuk fungsi, bukan program penuh. Jika solusi 17-byte Anda adalah program lengkap yang bekerja secara konsisten di seluruh proses, tidak apa-apa.
Mego
2

Racket 13 byte

lcm adalah fungsi bawaan di Racket:

(apply lcm l)

Pengujian:

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

Keluaran:

14
8
24
40
90
35
1144
3080
420
1260
2520
juga
sumber
Ahh. Bagaimana Anda bisa menggunakan sintaks itu. Saya selalu menyerah ketika saya mencoba belajar Racket.
Roman Gräf
1
Kata pertama dalam tanda kurung adalah nama prosedur, sisanya adalah argumennya. Jika argumen adalah prosedur, itu harus dalam kurung sendiri. Nilai (non-prosedur) ditulis tanpa tanda kurung. Saya menemukan itu menjadi bahasa tujuan umum yang sangat baik dengan keuntungan tambahan penekanan pada pemrograman fungsional. Berasal dari Lisp, orang juga mendapatkan perasaan menutupi area pemrograman itu.
rnso
Saya menemukan pengkodean kata kunci dan bahasa menjadi lebih mudah di Racket & Scheme daripada Lisp.
rnso
Ya, tetapi apakah saya mengatakan saya mengerti Lisp? Saya lebih suka bahasa seperti Jelly atau Java.
Roman Gräf
1
Perbedaan sintaks utama antara Java dan Racket adalah f (a, b) vs (fab), x + y + z vs (+ xyz), x == y vs (eq? Xy) dan x = 2 vs (define x 2) , atau jika sudah ditentukan, (atur! x 2). Juga tidak perlu mendeklarasikan tipe seperti public static void atau int char string dll. Semoga Anda tertarik dengan Racket lagi.
rnso
2

R, 36 byte (bukan bawaan)

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

Mengambil input. Kemudian menguji setiap bilangan bulat positif dengan mengambil mod.

pengguna5957401
sumber
Saya yakin Anda membutuhkan waktu catterakhir Andai
Giuseppe
@ Giuseppe ketika saya menjalankannya, nilai mencetak dengan baik.
user5957401
lihat pembahasannya di sini , tapi saya kira ec=Tlebih baik untuk +4 daripada +5 untuk cat().
Giuseppe
1
bagaimanapun juga, ini dapat di-golf v=scan();while(any((F=F+1)%%v)){};Fdengan cat()atau ec=Tmembuatnya masing-masing 40 atau 39 byte. Dan +1, pendekatan yang sangat bagus.
Giuseppe
1

Pyth, 9 byte

.U/*bZibZ

Program yang mengambil input daftar pada STDIN dan mencetak hasilnya.

Cobalah secara online atau verifikasi semua kasus uji

Bagaimana itu bekerja

.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
sumber
1

Haskell, 10 byte

foldr1 lcm

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

nimi
sumber
1

C #, 50 + 18 = 68 byte

50 byte untuk definisi metode, +18 byte untuk impor LINQ.

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

Hampir sama dengan banyak jawaban lainnya. Menghitung secara rekursif sampai menemukan LCM. Saya agak terkejut ini tidak mendapatkan StackOverflowException, jadi saya juga memiliki versi non-rekursif yang sebenarnya hanya 1 byte lebih lama.

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

Tidak Disatukan:

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
;
susu
sumber
1

Pip , 10 byte

W$+o%g++oo

Gunakan strategi "coba setiap angka sampai berhasil". Cobalah 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
sumber
1

PHP, 42 74 byte

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

lurus ke depan:
loop $fdari 1 ke atas; jika $f*$amembelah $btanpa sisa, LCM ditemukan.


Saya benar-benar telah membaca at least... ini kode untuk sejumlah parameter:

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

Loop $fdari 1 ke atas sementara loop dalam belum berjalan ke $ argc.
Loop $idari 2ke $argc-1sementara $f*$argv[1]membagi $argv[$i]tanpa sisa.
kedua loop rusak: cetak $f*$argument 1.

Titus
sumber
1

Prolog (SWI) , 46 byte

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

Cobalah online!

Solusi lain, 59 byte:

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

Python 3, 83 byte

import math,functools as i
t=lambda t:i.reduce(lambda a,b:int(a*b/math.gcd(a,b)),t)
Hydreigos
sumber
Selamat datang di PPCG!
Laikoni
Anda mungkin ingin memasukkan tautan ke situs pengujian online seperti Coba online! jadi lebih mudah bagi orang lain untuk memverifikasi jawaban Anda.
Laikoni
1

Brachylog v2, 8 byte

{×↙Xℕ₁}ᵛ

Cobalah online!

Lucu bagaimana langsung memetakan definisi yang diberikan dalam tantangan.

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

Solusi yang mencurigakan lambat tetapi jauh lebih singkat:

Brachylog v2, 5 byte

f⊇p~d

Cobalah online!

Mengambil input melalui variabel output dan memberikan output melalui variabel input. Robekan menembus empat kasus uji pertama tetapi saya masih menunggu pada yang kelima ... Biasanya, saya masih akan menjadikannya solusi utama saya dan hanya percaya bahwa itu bekerja dengan benar, tetapi saya tidak tahu mengapa itu belum menegaskan bahwa 90 adalah LCM 9, 6, 2, 1, 5ketika saya memberikan 90 dua puluh menit yang lalu.

(Sunting: Ini mengonfirmasi jawaban setelah tidak lebih dari 16 jam, dan menghasilkannya di samping LCM 5, 5, 7, 1, 1setelah sekitar dua hari.)

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

Dan predikat lain yang sama sekali berbeda yang secara tidak sengaja menerjemahkan solusi Brachylog v1 Fatalize:

Brachylog v2, 10 byte

;.gᵗ↔z%ᵛ0<

Cobalah online!

Ini diselamatkan dari solusi yang saya buat untuk tantangan ini sebelum saya menyadari output tidak terbatas menjadi bilangan bulat.

 .            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.
String yang tidak terkait
sumber
0

Pyth - 7 6 byte

Tidak ada builtin

*F{sPM

Cobalah online di sini .

Maltysen
sumber
4
Gagal [4], atau apa pun dengan faktor prima berulang.
isaacg