Постановка проблемы

Учитывая набор уникальных последовательных простых чисел (необязательно включая 2), генерируют произведения всех комбинаций первых степеней этих простых чисел - например, без повторов - а также 1. Например, учитывая набор {2, 3, 5, 7}, вы производите {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210}, потому что:

  1  =  1
  2  =  2
  3  =  3
  5  =  5
  6  =  2 x 3
  7  =  7
 10  =  2 x 5
 14  =  2 x 7
 15  =  3 x 5
 21  =  3 x 7
 30  =  2 x 3 x 5
 35  =  5 x 7
 42  =  2 x 3 x 7
 70  =  2 x 5 x 7
105  =  3 x 5 x 7
210  =  2 x 3 x 5 x 7

Обратите внимание, что если количество элементов вашего входного набора равно k, это даст вам 2 ^ k членов в вашем выходном наборе.

Правила / условия

1. Вы можете использовать любой язык. Стремитесь к наименьшему количеству символов исходного кода.
2. Ваше решение должно быть либо полной программой, либо полной функцией. Функция может быть анонимной (если ваш язык поддерживает анонимные функции).
3. Ваше решение должно поддерживать продукты как минимум до 2 ^ 31. Не беспокойтесь об обнаружении или обработке целочисленного переполнения, если вам передают числа, чей продукт слишком велик для представления. Однако, пожалуйста, укажите пределы ваших расчетов.
4. Вы можете принять список или набор и создать список или набор. Вы можете предположить, что вход отсортирован, но вы не обязаны производить отсортированный вывод.

Задний план

Когда или почему это полезно? Одним из мест, где это очень полезно, является создание таблицы множителей для параллельного состязания в алгоритме целочисленного факторинга, известном как факторизация квадратов, Там каждый нечетный множитель, который вы пробуете, уменьшает вероятность сбоя алгоритма (чтобы найти фактор) примерно на 50% на жестких полупростых числах. Таким образом, с набором порождающих простых чисел {3, 5, 7, 11}, который генерирует набор из 16 пробных множителей для параллельного состязания, алгоритм терпит неудачу примерно в 2 ^ –16 раз на жестких полуприцепах. Добавление 13 к списку простых чисел дает набор из 32 пробных множителей, снижая вероятность неудачи примерно до 2–32, что дает резкое улучшение результата без дополнительных вычислительных затрат (поскольку даже при увеличении вдвое большего числа множителей параллельно в среднем он все равно находит ответ в том же общем количестве шагов).

Чистый Баш, 32 байта

eval echo \$[{1,${1// /\}*{1,}}]

Читает список ввода (разделенный одним пробелом), переданный как аргумент командной строки.

Используются три различных расширения оболочки:

1. ${1// /\}*{1,}является расширение параметр , который заменяет пробелы 2 3 5 7с , }*{1,чтобы дать 2}*{1,3}*{1,5}*{1,7. \$[{1,и }]добавляются в начало и конец соответственно, чтобы дать \$[{1,2}*{1,3}*{1,5}*{1,7}]. \$[Является обратной косой черты экранированием для предотвращения попыток сделать арифметическое расширение на данном этапе.
2. \$[{1,2}*{1,3}*{1,5}*{1,7}]это расширение скобки . Поскольку расширение фигурных скобок обычно происходит перед расширением параметров , мы должны использовать evalвынуждение, чтобы расширение параметров происходило первым. Результатом расширения скобок является $[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7].
3. $[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7]это список арифметических расширений , которые затем оцениваются, чтобы дать список чисел, которые нам нужны.

Выход:

$ ./comboprime.sh "2 3 5 7"
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210
$

CJam, 13 байтов

1aq~{1$f*+}/p

Читает массив (например, [2 3 5 7]) из STDIN. Попробуйте онлайн.

Анонимная функция будет иметь тот же счетчик байтов:

{1a\{1$f*+}/}

Пример запуска

$ cjam <(echo '1aq~{1$f*+}/p') <<< '[]'
[1]
$ cjam <(echo '1aq~{1$f*+}/p') <<< '[2 3 5 7]'
[1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210]

Как это устроено

1a               " Push R := [1].              ";
  q~             " Read an array A from STDIN. ";
    {     }/     " For each a ∊ A:             ";
     1$f*+       "     R += { ra : r ∊ R }     ";
            p    " Print.                      ";

Хаскелл, 22

решение является анонимной функцией:

map product.mapM(:[1])

пример использования:

*Main> map product.mapM(:[1]) $ [2,3,5]
[30,6,10,2,15,3,5,1]

Объяснение:
(:[1]) это функция, которая с указанным номером xвозвращает список [x,1].
mapM(:[1])является функцией, которая предоставляет список чисел, отображает функцию (:[1])над ними и возвращает все возможные способы выбора элемента из каждого списка. например, mapM(:[1]) $ [3,4]сначала сопоставляет функцию для получения [[3,1] , [4,1]]. тогда возможный выбор [3,4](выбор первого числа обоих), [3,1] [1,4]и [1,1]поэтому он возвращается [[3,4],[3,1],[1,4],[1,1]].

затем map productсопоставляет все варианты и возвращает их продукты, которые являются желаемым результатом.

эта функция полиморфна по своему типу, что означает, что она может работать со всеми типами чисел. Вы можете ввести его в список Intи результат будет список, Intно также может быть применен к списку типаIntegerи вернуть список Integer. это означает, что поведение переполнения определяется не этой функцией, а типом ввода (экспрессивная система типов yay Haskell :))

Mathematica, 18 17 байт

1##&@@@Subsets@#&

Это анонимная функция. Назови это как

1##&@@@Subsets@#&[{2,3,5,7}]

Обновление: C (функция f), 92

Даже как функция, это все еще самая длинная запись здесь. Я впервые передал массив неизвестной длины в качестве аргумента функции в C, и, очевидно, у функции C нет возможности узнать длину переданного ей массива, поскольку аргумент передается как указатель ( независимо от используемого синтаксиса). Следовательно, второй аргумент необходим для указания длины.

Я сохранил вывод в stdout, потому что установка целочисленного массива и его возврат почти наверняка будут дольше.

Спасибо Деннису за советы.

См. Функцию f(92 символа, исключая ненужные пробелы) в тестовых программах ниже.

Вывод через printf

j;

f(int c,int*x){
  int p=1,i;
  for(i=c<<c;i--;p=i%c?p:!!printf("%d ",p))p*=(i/c>>i%c)&1?1:x[i%c];
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y);
}

Вывод через указатель массива

j,q[512];

f(int c,int*x,int*p){
    for(int i=-1;++i-(c<<c);p[i/c]*=(i/c>>i%c)&1?1:x[i%c])i%c||(p[i/c]=1);
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y,q);
  for(j=1<<d;j--;)printf("%d ",q[j]);
}

С (программа), 108

исключая ненужные пробелы.

p=1,i;
main(int c,char**v){
  c-=1;
  for(i=c<<c;i--;i%c||(printf("%d ",p),p=1))(i/c>>i%c)&1||(p*=atoi(v[i%c+1]));
}

Ввод из командной строки, вывод в stdout. Си не выиграет здесь, но, возможно, я попытаюсь перейти к функции завтра.

В основном мы перебираем все 1<<cкомбинации простых чисел, причем каждый бит i/cсвязан с наличием или отсутствием определенного простого числа в произведении. «Внутренний цикл» i%cпроходит через простые числа, умножая их в соответствии со значением, i/c.когда значение i%cдостигает 0, продукт выводится, а затем устанавливается на 1 для следующей «внешней» итерации.

любопытно, что printf("%d ",p,p=1)это не работает (всегда печатает 1.) Я не первый раз наблюдаю странное поведение, когда значение используется в printfи присваивается позже в той же скобке. В этом случае возможно, что вторая запятая рассматривается не как разделитель аргументов, а как оператор.

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

$ ./a 2 3 5 7
1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210

Haskell, 27 байт

Это реализация Haskell ответа CJam @ sudo как анонимной функции. Он не побьет потрясающее решение @proud haskeller на Haskell, но я все равно оставлю его здесь.

foldr((=<<)(++).map.(*))[1]

Объяснение: foldr принимает двоичную функцию, значение и список. Затем он заменяет каждую ячейку минусов в списке путем применения функции, и конец списка по значению, например: foldr f v [a,b,c] == f a (f b (f c v)). Наше значение - это одноэлементный список, содержащий 1двоичную функцию f = (=<<)(++).map.(*). Теперь fберет число n, делает функцию, (n*)которая умножается на n, делает из нее функцию, g = map(n*)которая применяет эту функцию ко всем элементам списка и передает эту функцию (=<<)(++). Здесь (++)функция конкатенации, и (=<<)является монадическим связывают , которая в данном случае принимает (++)и g, и дает функцию , которая принимает в списке, применяетсяg к его копии, и объединяет их.

Вкратце: начните с [1]и для каждого числа nв списке ввода возьмите копию текущего списка, умножьте все на nи добавьте ее в текущий список.

Питон: 55 символов

f=lambda l:l and[x*l[0]for x in f(l[1:])]+f(l[1:])or[1]

Рекурсивно генерирует продукты, выбирая включить или исключить каждое число по очереди.

PARI / GP , 26 байт

v->divisors(factorback(v))

Более длинные версии включают

v->divisors(prod(i=1,#v,v[i]))

(30 байт) и

v->divisors(fold((x,y)->x*y,v))

(31 байт).

Обратите внимание, что если бы ввод был матрицей факторизации, а не набором, 18 байтов можно было бы сохранить, используяdivisors один. Но преобразование набора в матрицу факторизации, кажется, занимает более 18 байтов. (Я могу сделать это в 39 байтах напрямую v->concat(Mat(v~),Mat(vectorv(#v,i,1)))или в 24 байта путем умножения и перефакторинга v->factor(factorback(v)), кто-нибудь может сделать лучше?)

Мудрец - 36 34

По сути, так же, как решение Мартина Бюттнера , если я правильно понимаю. Как я уже упоминал в комментарии, я мог бы также опубликовать это как ответ.

lambda A:map(prod,Combinations(A))

Это анонимная функция, которую, например, можно вызвать следующим образом:

(lambda A:map(prod,Combinations(A)))([2,3,5,7])

J (20)

Это оказалось дольше, чем я надеялся или ожидал. Тем не менее: короче, чем haskel!

*/@:^"1#:@i.@(2&^)@#

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

    f=:*/@:^"1#:@i.@(2&^)@#
    f 2 3 5 7
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210

Это работает для любого набора чисел, а не только для простых чисел. Кроме того, простые числа могут быть неограниченного размера, если массив имеет постфикс x:2 3 5 7x

05AB1E , 2 байта

æP

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

объяснение

æ   # powerset
 P  # product

R, 56 байт

r=1;for(i in 1:length(s))r=c(r,apply(combn(s,i),2,prod))

Я рассматриваю здесь, что s - это множество (и список). Я уверен, что это можно сделать еще короче. Я увижу.

PHP, 97 байт

<?for(;$i++<array_product($a=$_GET[a]);){$t=$i;foreach($a as$d)$t%$d?:$t/=$d;if($t<2)echo"$i\n";}