Énoncé du problème

Étant donné un ensemble de nombres premiers uniques consécutifs (ne comprenant pas nécessairement 2), générez les produits de toutes les combinaisons de premières puissances de ces nombres premiers - par exemple, pas de répétitions - et également 1. Par exemple, étant donné l'ensemble {2, 3, 5, 7}, vous produisez {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210} parce que:

  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

Notez que si la cardinalité de votre jeu d'entrée est k, cela vous donnera 2 ^ k membres dans votre jeu de sortie.

Règles / Conditions

1. Vous pouvez utiliser n'importe quelle langue. Visez le plus petit nombre de caractères du code source.
2. Votre solution doit être soit un programme complet, soit une fonction complète. La fonction peut être anonyme (si votre langue prend en charge les fonctions anonymes).
3. Votre solution doit pouvoir prendre en charge des produits jusqu'à au moins 2 ^ 31. Ne vous inquiétez pas de détecter ou de gérer un débordement d'entier si vous passez des nombres dont le produit est trop grand pour être représenté. Veuillez cependant indiquer les limites de vos calculs.
4. Vous pouvez accepter une liste ou un ensemble et produire une liste ou un ensemble. Vous pouvez supposer que l'entrée est triée, mais vous n'êtes pas obligé de produire une sortie triée.

Contexte

Quand ou pourquoi est-ce utile? Il est très utile de générer une table de multiplicateurs pour faire la course en parallèle dans un algorithme de factorisation d'entier connu sous le nom de factorisation de formes carrées. Là, chaque multiplicateur impair que vous essayez diminue la probabilité que l'algorithme échoue (pour trouver un facteur) d'environ 50% sur les demi-durs durs. Ainsi, avec l'ensemble de génération de nombres premiers {3, 5, 7, 11}, qui produit un ensemble de 16 multiplicateurs d'essai pour faire la course en parallèle, l'algorithme échoue environ 2 ^ –16 du temps sur les demi-durs durs. L'ajout de 13 à la liste des nombres premiers produit un ensemble de 32 multiplicateurs d'essai, réduisant le risque d'échec à environ 2 ^ –32, ce qui donne une amélioration drastique des résultats sans frais de calcul supplémentaires (car même avec deux fois plus de multiplicateurs qui courent en parallèle, sur moyenne, il trouve toujours la réponse dans le même nombre total d'étapes).

Pure Bash, 32 octets

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

Lit la liste d'entrée (séparée par un espace) passée comme argument de ligne de commande.

Trois extensions de shell différentes sont utilisées:

1. ${1// /\}*{1,}est une extension de paramètre qui remplace les espaces 2 3 5 7par }*{1,pour donner 2}*{1,3}*{1,5}*{1,7. \$[{1,et }]sont ajoutés respectivement au début et à la fin pour donner \$[{1,2}*{1,3}*{1,5}*{1,7}]. La \$[barre oblique inverse est utilisée pour empêcher les tentatives de développement arithmétique à ce stade.
2. \$[{1,2}*{1,3}*{1,5}*{1,7}]est une extension d'accolade . Étant donné que l' expansion d'accolade se produit généralement avant l'expansion des paramètres , nous devons utiliser evalpour forcer l'expansion des paramètres à se produire en premier. Le résultat de l'expansion de l'accolade est $[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]est une liste d' extensions arithmétiques , qui sont ensuite évaluées pour donner la liste des nombres dont nous avons besoin.

Sortie:

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

CJam, 13 octets

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

Lit un tableau (par exemple, [2 3 5 7]) à partir de STDIN. Essayez-le en ligne.

Une fonction anonyme aurait le même nombre d'octets:

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

Exemple d'exécution

$ 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]

Comment ça marche

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

Haskell, 22

la solution est une fonction anonyme:

map product.mapM(:[1])

exemple d'utilisation:

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

explication:
(:[1]) est une fonction qui, étant donné un nombre, xrenvoie la liste [x,1].
mapM(:[1])est une fonction qui, à partir d'une liste de nombres, mappe la fonction (:[1])sur eux et renvoie toutes les manières possibles de choisir un élément dans chaque liste. par exemple, mapM(:[1]) $ [3,4]mappe d'abord la fonction à obtenir [[3,1] , [4,1]]. alors les choix possibles sont [3,4](en choisissant le premier nombre des deux) [3,1] [1,4]et [1,1]ainsi il revient [[3,4],[3,1],[1,4],[1,1]].

puis des map productcartes sur tous les choix et retourne leurs produits, qui sont la sortie désirée.

cette fonction est polymorphe dans son type, ce qui signifie qu'elle peut fonctionner sur tous les types de nombres. vous pouvez entrer une liste de Intet le résultat serait une liste de Intmais pourrait également être appliqué sur une liste de typeIntegeret retourner une liste de Integer. cela signifie que le comportement de débordement n'est pas spécifié par cette fonction mais par le type de l'entrée (yay Haskell's expressive type system :))

Mathematica, 18 17 octets

1##&@@@Subsets@#&

C'est une fonction anonyme. Appelez ça comme

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

Mise à jour: C (fonction f), 92

Même en tant que fonction, c'est toujours l'entrée la plus longue ici. C'est la première fois que je passe un tableau de longueur inconnue comme argument de fonction en C, et apparemment il n'y a aucun moyen pour une fonction C de connaître la longueur d'un tableau qui lui est passé, car l'argument est passé comme pointeur ( quelle que soit la syntaxe utilisée). Un deuxième argument est donc nécessaire pour indiquer la longueur.

J'ai gardé la sortie sur stdout, car configurer un tableau entier et le renvoyer serait presque certainement plus long.

Merci à Dennis pour les conseils.

Voir la fonction f(92 caractères hors espaces blancs inutiles) dans les programmes de test ci-dessous.

Sortie via 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);
}

Sortie via un pointeur de tableau

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

C (programme), 108

excluant les espaces inutiles.

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

Entrée depuis la ligne de commande, sortie vers la sortie standard. C ne va pas gagner ici, mais peut-être que j'essaierai de convertir en fonction demain.

Fondamentalement, nous parcourons toutes les 1<<ccombinaisons de nombres premiers, chaque bit i/cétant associé à la présence ou à l'absence d'un nombre premier particulier dans le produit. La "boucle interne" i%cparcourt les nombres premiers, en les multipliant selon la valeur de i/c.Lorsque i%catteint 0, le produit est sorti, puis défini sur 1 pour l'itération "externe" suivante.

curieusement, printf("%d ",p,p=1)ne fonctionne pas (il imprime toujours un 1.) Ce n'est pas la première fois que je vois un comportement étrange lorsqu'une valeur est utilisée dans a printfet attribuée plus tard dans le même crochet. Il est possible dans ce cas que la deuxième virgule ne soit pas traitée comme un séparateur d'arguments, mais plutôt comme un opérateur.

Usage

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

Haskell, 27 octets

Il s'agit d'une implémentation Haskell de la réponse CJam de @ sudo en tant que fonction anonyme. Cela ne battra pas la formidable solution Haskell de @proud haskeller, mais je la déposerai quand même.

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

Explication: foldr prend une fonction binaire, une valeur et une liste. Ensuite , il remplace chaque cellule de contre dans la liste par une application de la fonction, et la fin de la liste par la valeur, comme ceci: foldr f v [a,b,c] == f a (f b (f c v)). Notre valeur est une liste à un élément contenant 1, et la fonction binaire est f = (=<<)(++).map.(*). Maintenant, fprend un nombre n, crée une fonction (n*)qui multiplie par n, en fait une fonction g = map(n*)qui applique cette fonction à tous les éléments d'une liste et alimente cette fonction (=<<)(++). Ici, (++)est la fonction de concaténation, et (=<<)est une liaison monadique , qui dans ce cas prend (++)et g, et donne une fonction qui prend dans une liste, s'appliqueg à une copie de celui-ci, et concatène les deux.

En bref: commencez par [1], et pour chaque numéro nde la liste d'entrée, prenez une copie de la liste actuelle, multipliez tout par net ajoutez-la à la liste actuelle.

Python: 55 caractères

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

Génère récursivement les produits en choisissant d'inclure ou d'exclure chaque numéro tour à tour.

PARI / GP , 26 octets

v->divisors(factorback(v))

Les versions plus longues incluent

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

(30 octets) et

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

(31 octets).

Notez que si l'entrée était une matrice de factorisation plutôt qu'un ensemble, 18 octets pouvaient être enregistrés en utilisant divisorsseuls. Mais la conversion d'un ensemble en matrice de factorisation semble prendre plus de 18 octets. (Je peux le faire en 39 octets directement v->concat(Mat(v~),Mat(vectorv(#v,i,1)))ou en 24 octets en multipliant et en refactorisant v->factor(factorback(v)), quelqu'un peut-il faire mieux?)

Sauge - 36 34

Essentiellement, la même que la solution de Martin Büttner , si je comprends bien. Comme je l'ai mentionné dans un commentaire, je pourrais aussi bien l'afficher comme réponse.

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

Il s'agit d'une fonction anonyme, qui peut par exemple être appelée comme suit:

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

J (20)

Cela s'est avéré plus long que ce que j'espérais ou espérais. Encore: plus court que haskel!

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

Usage:

    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

Cela fonctionne pour tout ensemble de nombres, pas seulement pour les nombres premiers. De plus, les nombres premiers peuvent être de taille illimitée, tant que le tableau a le suffixe x:2 3 5 7x

05AB1E , 2 octets

æP

Essayez-le en ligne!

Explication

æ   # powerset
 P  # product

R, 56 octets

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

Je considère ici que s est l'ensemble (et une liste). Je suis sûr que cela peut être encore plus court. Je verrai.

PHP, 97 octets

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