Наименьший общий множитель

31

Наименьшее общее кратное из набора положительных целых чисел Aявляется наименьшим положительным целым числом, Bтаким образом, что для каждого kв Aсуществует положительное целое число, nтакое что k*n = B.

Учитывая как минимум два натуральных числа в качестве входных данных, выведите их наименьшее общее кратное.

правила

  • Встроенные функции разрешены, но если ваше решение использует их, рекомендуется включить альтернативное решение, которое не использует встроенные функции GCD / LCM. Тем не менее, альтернативное решение не будет учитываться при подсчете очков, поэтому оно не является обязательным.
  • Все входы и выходы будут в пределах исходного представления для вашего языка. Если ваш язык изначально обладает произвольно большими целыми числами, то ваше решение должно работать с произвольно большими входами и выходами.

Контрольные примеры

[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
источник
6
Потому что это довольно частое заблуждение: формула LCM (a, b) = ab / GCD (a, b) не распространяется на более чем два числа (или, в этом отношении, на одно число!).
Грег Мартин

Ответы:

4

На самом деле, 12 1 байт

Предложения по игре в гольф все еще приветствуются, хотя я не уверен, как улучшить встроенный в LCM. Попробуйте онлайн!

12-байтовая версия без встроенного. Предложения по игре в гольф приветствуются. Попробуйте онлайн!

╗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
источник
Ты же понимаешь, что тебе разрешено использовать встроенные функции, верно?
Mego
1
@Mego, я добавлю это, но, насколько я понимаю, встроенные функции были обескуражены, поэтому я сначала не использовал их.
Sherlock9
1
Встроенные разрешены. Они совсем не обескуражены - я просто хотел поощрять включение не встроенных решений, потому что они часто намного интереснее встроенных.
Мего
1
Я прочитал это как на самом деле, 1 байт .
programmer5000
2
@ programmer5000 Я думаю, именно поэтому этот язык и называется на самом деле ...
Сократов Феникс
17

JavaScript (ES6), 36 байт

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

Начиная с 1первого числа, которое можно разделить на всех.

Хеди
источник
Конечно ... Я думал о создании цикла с этой техникой, но рекурсия намного короче.
ETHproductions
1
Это гениально ... Если я вспомню, someвозвращает истину, если хотя бы один элемент в массиве удовлетворяет условию, верно?
WallyWest
11

Желе , 3 байта

æl/

Уменьшает на LCM. Попробуйте онлайн! или проверьте все контрольные примеры .

Альтернативная версия, 6 байт

ÆE»/ÆẸ

Попробуйте онлайн! или проверьте все контрольные примеры .

Как это работает

Æ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.
Деннис
источник
8

Python, 69 65 52 50 байт

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

2 байта сохранены благодаря Денису!

Довольно простое рекурсивное решение, вам нужно будет немного увеличить предел рекурсии, чтобы некоторые тестовые примеры работали.

Loovjo
источник
1
anyберет генератор; вам не нужны скобки.
Деннис
3
A=lambda l,i=1:all(i%a<1for a in l)or-~A(l,i+1)сохраняет еще несколько байтов.
Деннис
8

MATL , 7 байт

&YFX>^p

Нет встроенного

Попробуйте онлайн!

объяснение

Давайте возьмем входные данные [8, 2, 1, 10]в качестве примера.

&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

РЕДАКТИРОВАТЬ (9 июня 2017 г.): YFв выпуске 20.1.0 были изменены два выхода : нефакторные простые числа и их (нулевые) показатели пропущены. Это не влияет на приведенный выше код, который работает без каких-либо изменений.

Луис Мендо
источник
6

Юлия (3 байта) [Работа над не встроенным]

lcm     # Using LCM built-in (3 Bytes)

Как отметил Деннис, я постоянно забываю, что Джулия автоматически векторизует входные данные.

Пример:

println(lcm(1,2,3,4,5,6,7,8,9)) #Prints 2520
Урна волшебного осьминога
источник
6

PowerShell v2 +, 73 60 байт

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

Принимает ввод $a, зацикливается вверх от $i=1с $i++, основываясь на условном выражении. Условие ($a|?{!($i%$_)}).countбыть -nВЗ eкаче к $a.count. Это означает, что цикл заканчивается, когда элементы $a, являющиеся делителями, $iравны элементам $a. Затем $iна конвейере остается одиночное , и вывод неявный.

Тестовые случаи

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
источник
4

Mathematica, 3 байта

LCM

Использование:

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

Out[1]= 2520
alephalpha
источник
6
День, когда Mathematica совпал с Jelly, это день, который я никогда не думал, что увижу.
Стивен Х.
3

Чеддер, 33 байта

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

Ничего супер нового.

Ungolfed

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

В основном это начинается с одного и продолжает увеличиваться, пока не найдет LCM

Downgoat
источник
3

JavaScript (ES6), 63 59 байт

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

Рекурсивно находит LCM из последних двух элементов.

ETHproductions
источник
Вот каково было бы мое решение:a=>a.reduce((l,n)=>l*n/(g=(m,n)=>n?g(n,m%n):m)(l,n))
Нейл
@Neil Вы можете опубликовать это, если хотите. Я сомневаюсь, что моя техника может быть
настолько
3

Дьялог АПЛ, 2 байта

∧/

Уменьшает на LCM. Проверьте это на TryAPL .

Деннис
источник
4
Поздравляю на 100к!
Медь
3

JavaScript (ES6), 52 байта

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

Я reduceсделал этот ответ столько, сколько мог, но, очевидно, я не собираюсь приближаться к простоте ответа @ Хеди.

Нил
источник
3

Java 8, 75 59 121 89 байт

Использует евклидов алгоритм и тот факт, что LCM (A, B) = A * B / GCD (A, B)

  • 16 байтов. Благодаря @carusocomputing
  • Добавлен мульти-ввод + 62 байта
  • 32 байта выкл. Благодаря @ Оливье Грегуар

Код:

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

Удалить разрывы строк:

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;}
Роман Греф
источник
Технически это фрагмент кода, но если вы добавите его, n->{...}я верю, что он станет действительным Java 8.
Урна с магическим осьминогом
Спасибо. Я пытаюсь привыкнуть видеть лямбду в Java. С лямбдой вы, вероятно, можете сыграть в гольф. Но я не знаю как.
Роман Грэф
Да, все эти вещи - запоздалая мысль в Java; вам, вероятно, будет лучше изучить его на Python :).
Волшебная Урна Осьминога
Если я что-то упустил, он не поддерживает более двух входов
pinkfloydx33
Если вычислять НОД, вы можете играть в гольф гораздо больше: int g(int a,int b){return b<1?a:g(b,a%b);}. LCM может затем стать int l(int[]a){int l=1;for(int n:a)l=l*n/g(l,n);return l;}, в общей сложности, 99 байтов.
Оливье Грегуар
2

Perl 6 , 10 байт

{[lcm] @_}

в основном так же, как:

sub ( *@_ ) { @_.reduce: &infix:< lcm > }
Брэд Гилберт b2gills
источник
2

J 11 байт

>./&.(_&q:)

Существует решение для 3 байтов с использованием встроенного LCM.

*./

объяснение

>./&.(_&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
миль
источник
2

CJam, 18 17 16 байтов

1 байт сохранен благодаря Мартину Эндеру.

Увеличивается, пока не будет найден LCM.

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

Попробуйте онлайн

Neorej
источник
1
Я не совсем знаком с CJam, но правило повторного использования предназначено для функций, а не для полных программ. Если ваше 17-байтовое решение представляет собой полноценную программу, которая последовательно работает на всех этапах, это нормально.
Mego
2

Ракетка 13 байт

lcm - встроенная функция в Racket:

(apply lcm l)

Тестирование:

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

Выход:

14
8
24
40
90
35
1144
3080
420
1260
2520
rnso
источник
Ааа. Как вы можете использовать этот синтаксис. Я всегда сдавался, когда пытался выучить ракетку.
Роман Греф
1
Первое слово в скобках - это имя процедуры, остальные - ее аргументы. Если аргумент является процедурой, он должен быть в своих скобках. Значения (непроцедуры) пишутся без скобок. Я считаю, что это отличный язык общего назначения с дополнительным преимуществом упора на функциональное программирование. Происходя из Lisp, мы также получаем представление о той области программирования.
rnso
Я считаю, что кодирование ключевых слов и языка проще в Racket & Scheme, чем в Lisp.
rnso
Да, но я сказал, что понимаю Лисп? Мне больше нравятся такие языки, как Jelly или Java.
Роман Греф
1
Основное различие синтаксиса между Java и Racket: f (a, b) против (fab), x + y + z против (+ xyz), x == y против (eq? Xy) и x = 2 против (определите x 2) или, если уже определено, (установите! x 2). Также не нужно объявлять типы, такие как public static void или int char string и т. Д. Надеюсь, что вы снова заинтересовались Racket.
rnso
2

R, 36 байт (не встроено)

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

Принимает вход. Затем проверяет каждое положительное целое число, взяв мод.

user5957401
источник
Я полагаю, вам нужно в catпоследний разi
Джузеппе
@ Giuseppe, когда я запускаю его, значение печатается нормально.
user5957401
смотрите обсуждение здесь , но я думаю, что ec=Tэто хорошо для +4, а не +5 для cat().
Джузеппе
1
независимо, это может быть golfed вниз некоторые v=scan();while(any((F=F+1)%%v)){};Fс cat()или ec=Tделая это 40 или 39 байт соответственно. И +1, очень хороший подход.
Джузеппе
1

Pyth, 9 байт

.U/*bZibZ

Программа, которая принимает ввод списка в STDIN и печатает результат.

Попробуйте онлайн или проверьте все тесты

Как это работает

.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
источник
1

Haskell, 10 байт

foldr1 lcm

Пример использования: foldl1 lcm [5,2,9,10,3,4,4,4,7]-> 1260.

Ними
источник
1

C #, 50 + 18 = 68 байт

50 байтов для определения метода, +18 байтов для импорта LINQ.

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

Почти так же, как и многие другие ответы. Отсчитывает рекурсивно, пока не найдет LCM. Я был немного удивлен, что не получил StackOverflowException, поэтому у меня также есть нерекурсивная версия, которая на самом деле всего на 1 байт длиннее.

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

Ungolfed:

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
;
молоко
источник
1

Пип , 10 байт

W$+o%g++oo

Использует стратегию «пробуй каждое число, пока не сработает». Попробуйте онлайн!

            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
источник
1

PHP, 42 74 байта

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

прямо:
петля $fот 1 вверх; если $f*$aразделить $bбез остатка, LCM найден.


Я полностью перечитал at least... вот код для любого количества параметров:

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

Цикл $fот 1 и выше, в то время как внутренний цикл не работает до $ argc.
Цикл $iот 2до $argc-1пока $f*$argv[1]делит $argv[$i]без остатка.
обе петли сломаны: печать $f*$argument 1.

Titus
источник
1

Python 3, 83 байта

import math,functools as i
t=lambda t:i.reduce(lambda a,b:int(a*b/math.gcd(a,b)),t)
Hydreigos
источник
Добро пожаловать в PPCG!
Лайкони
Возможно, вы захотите добавить ссылку на сайт онлайн-тестирования, например, попробуйте онлайн! чтобы другим было проще проверить ваш ответ.
Лайкони
1

Brachylog v2, 8 байт

{×↙Xℕ₁}ᵛ

Попробуйте онлайн!

Забавно, насколько прямо это соответствует определению, данному в задании.

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

Подозрительно медленное, но значительно более короткое решение:

Brachylog v2, 5 байт

f⊇p~d

Попробуйте онлайн!

Принимает ввод через выходную переменную и дает вывод через входную переменную. Проходит первые четыре тестовых случая, но я все еще жду пятого ... Обычно я все равно делаю это своим основным решением и просто верю, что оно работает правильно, но я не знаю, почему это не так подтвердил, что 90 является LCM, 9, 6, 2, 1, 5когда я дал ему 90 минут назад.

(Изменить: он подтвердил ответ не позднее, чем через 16 часов, и сгенерировал его вместе с LCM 5, 5, 7, 1, 1примерно через два дня.)

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

И еще один совершенно другой предикат, который случайно более или менее переводит решение Fatalize Brachylog v1:

Brachylog v2, 10 байт

;.gᵗ↔z%ᵛ0<

Попробуйте онлайн!

Это было спасено от решения, которое я принял для этой задачи, прежде чем я понял, что результат не ограничен целым числом.

 .            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.
Несвязанная строка
источник