Erklärung des Problems
Erzeugen Sie aus einer Menge eindeutiger, aufeinanderfolgender Primzahlen (nicht notwendigerweise einschließlich 2) die Produkte aller Kombinationen der ersten Potenzen dieser Primzahlen - z. B. keine Wiederholungen - und auch 1. Wenn Sie beispielsweise die Menge {2, 3, 5, 7} erzeugen Sie {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210}, weil:
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
Beachten Sie, dass wenn die Kardinalität Ihrer Eingabemenge k ist, dies Ihnen 2 ^ k Elemente in Ihrer Ausgabemenge gibt.
Regeln / Bedingungen
- Sie können eine beliebige Sprache verwenden. Streben Sie die kleinste Zeichenanzahl des Quellcodes an.
- Ihre Lösung muss entweder ein vollständiges Programm oder eine vollständige Funktion sein. Die Funktion kann anonym sein (wenn Ihre Sprache anonyme Funktionen unterstützt).
- Ihre Lösung sollte Produkte bis mindestens 2 ^ 31 unterstützen können. Machen Sie sich keine Sorgen über die Erkennung oder Behandlung von Integer-Überläufen, wenn Ihnen Zahlen übergeben werden, deren Produkt zu groß ist, um dargestellt zu werden. Bitte geben Sie jedoch die Grenzen Ihrer Berechnungen an.
- Sie können entweder eine Liste oder ein Set akzeptieren und entweder eine Liste oder ein Set erstellen. Sie können davon ausgehen, dass die Eingabe sortiert ist, müssen jedoch keine sortierte Ausgabe erstellen.
Hintergrund
Wann oder warum ist das sinnvoll? Ein Ort, an dem es sehr nützlich ist, eine Tabelle mit Multiplikatoren zu erstellen, die in einem Ganzzahlfaktor-Algorithmus, der als Square Forms Factorization bezeichnet wird, parallel laufen. Dort verringert jeder ungerade Multiplikator, den Sie versuchen, die Wahrscheinlichkeit, dass der Algorithmus ausfällt (um einen Faktor zu finden), auf harten Halbwerten um ungefähr 50%. Mit der Menge der generierenden Primzahlen {3, 5, 7, 11}, die eine Menge von 16 parallel laufenden Testmultiplikatoren ergibt, versagt der Algorithmus ungefähr 2 ^ –16 der Zeit auf harten Halbzeiten. Das Hinzufügen von 13 zur Liste der Primzahlen ergibt einen Satz von 32 Testmultiplikatoren, wodurch die Wahrscheinlichkeit eines Ausfalls auf ungefähr 2 ^ –32 verringert wird, was eine drastische Ergebnisverbesserung ohne zusätzlichen Rechenaufwand zur Folge hat (da selbst bei doppelt so vielen parallel laufenden Multiplikatoren weiter Durchschnittlich findet es die Antwort immer noch in der gleichen Anzahl von Schritten).
quelle
1 0
bash --version
CJam, 13 Bytes
Liest ein Array (zB
[2 3 5 7]
) aus STDIN. Probieren Sie es online aus.Eine anonyme Funktion hätte die gleiche Byteanzahl:
Beispiellauf
Wie es funktioniert
quelle
Haskell, 22
Die Lösung ist eine anonyme Funktion:
Beispielverwendung:
erklärung:
(:[1])
ist eine funktion, die mit einerx
nummer die liste liefert[x,1]
.mapM(:[1])
ist eine Funktion, die eine Liste von Zahlen angibt, die die Funktion(:[1])
über ihnen abbildet und alle möglichen Möglichkeiten zur Auswahl eines Elements aus jeder Liste zurückgibt. Zum BeispielmapM(:[1]) $ [3,4]
ordnet zuerst die Funktion zu, die abgerufen werden soll[[3,1] , [4,1]]
. dann sind die möglichen Wahlen[3,4]
(die erste Zahl von beiden wählend)[3,1]
[1,4]
und[1,1]
so gibt es zurück[[3,4],[3,1],[1,4],[1,1]]
.Anschließend
map product
werden alle Auswahlmöglichkeiten zugeordnet und die gewünschten Produkte zurückgegeben.Diese Funktion ist in ihrem Typ polymorph, was bedeutet, dass sie auf alle Arten von Zahlen angewendet werden kann. Sie könnten eine Liste von eingeben
Int
und das Ergebnis wäre eine Liste vonInt
, könnte aber auch auf eine Liste vom Typ angewendet werdenInteger
und eine Liste von zurückgebenInteger
. Dies bedeutet, dass das Überlaufverhalten nicht durch diese Funktion, sondern durch den Typ der Eingabe festgelegt wird (yay Haskells expressives Typensystem :)).quelle
Integer
ist ein unbegrenzter ganzzahliger Typ. Es gibt auchInt
eine 32-Bit-Ganzzahl, aber das ist meistens nur eine Legacy-Sache.Mathematica,
1817 BytesDas ist eine anonyme Funktion. Nenne es so
quelle
×@@@𝒫@#
sollte unschlagbar sein.(*/@#~2#:@i.@^#)
16 Zeichen in J;)Update: C (Funktion f), 92
Auch als Funktion ist dies immer noch der längste Eintrag hier. Es ist das erste Mal, dass ich ein Array unbekannter Länge als Funktionsargument in C übergeben habe, und anscheinend gibt es für eine C-Funktion keine Möglichkeit, die Länge eines an sie übergebenen Arrays zu ermitteln, da das Argument als Zeiger übergeben wird ( unabhängig von der verwendeten Syntax). Daher ist ein zweites Argument erforderlich, um die Länge anzugeben.
Ich habe die Ausgabe auf stdout gehalten, da das Einrichten und Zurückgeben eines Integer-Arrays mit ziemlicher Sicherheit länger dauern würde.
Danke an Dennis für die Tipps.
Siehe die Funktion
f
(92 Zeichen ohne unnötige Leerzeichen) in den folgenden Testprogrammen.Ausgabe über printf
Ausgabe über Array Pointer
C (Programm), 108
ohne unnötige Leerzeichen.
Eingabe von der Kommandozeile, Ausgabe nach stdout. C wird hier nicht gewinnen, aber vielleicht werde ich morgen versuchen, in eine Funktion zu konvertieren.
Grundsätzlich durchlaufen wir alle
1<<c
Kombinationen von Primzahlen, wobei jedes Biti/c
mit dem Vorhandensein oder Fehlen einer bestimmten Primzahl im Produkt verknüpft ist. Die "innere Schleife"i%c
durchläuft die Primzahlen und multipliziert sie mit dem Wert voni/c.
Wenni%c
0 erreicht wird, wird das Produkt ausgegeben und für die nächste "äußere" Iteration auf 1 gesetzt.Seltsamerweise
printf("%d ",p,p=1)
funktioniert das nicht (es gibt immer eine 1 aus). Dies ist nicht das erste Mal, dass ich ein merkwürdiges Verhalten sehe, wenn ein Wert in a verwendetprintf
und später in derselben Klammer zugewiesen wird. In diesem Fall wird das zweite Komma möglicherweise nicht als Argumenttrennzeichen, sondern als Operator behandelt.Verwendung
quelle
-Wsequence-point
oder-Wall
beschwert sich GCC.c-=1
zuc--
oder sogar verwenden ,i=--c<<c
wenn Sie UB nichts dagegen (mit GCC zu arbeiten scheint). 2. Beide Verwendungen von||
können durch ternäre Operatoren ersetzt werden:p=i%c?p:!!printf("%d ",p)
undp*=(i/c>>i%c)&1?1:atoi(v[i%c+1])
c-=1
Ich hätte es nicht verpassen sollen, aber es war eine schnelle Fehlerbehebung, weil ich vergessen hatte, dass argv (der Programmname) eine zusätzliche Zeichenfolgei=..c<<c
enthält, die auf GCC / cygwin funktioniert, aber ich habe mein Original verlassen programmieren wie es ist und zu einer Funktion übergehen. Ich habe gerade erfahren, dasssizeof
dies bei Arrays, die als Funktionsargumente übergeben wurden , nicht funktioniert. Ich habe Ihre Vorschläge für ternäre Operatoren in die Funktion aufgenommen. Ich bin bei der Ausgabe auf stdout geblieben, da ich keine kurze Möglichkeit sehe, ein Array zurückzugeben.Haskell, 27 Bytes
Dies ist eine Haskell-Implementierung von @ sudos CJam-Antwort als anonyme Funktion. Es wird die großartige Haskell-Lösung von @proud haskeller nicht schlagen, aber ich werde es trotzdem hier ablegen.
Erläuterung:
foldr
Nimmt eine Binärfunktion, einen Wert und eine Liste auf. Dann ersetzt es jede Nachteile Zelle in der Liste durch eine Anwendung der Funktion, und das Ende der Liste durch den Wert, wie folgt aus :foldr f v [a,b,c] == f a (f b (f c v))
. Unser Wert ist eine Ein-Element-Liste, die1
die Binärfunktion enthältf = (=<<)(++).map.(*)
. Nimmt nunf
eine Zahln
, erstellt eine Funktion(n*)
, die mit multipliziert wirdn
, erstellt daraus eine Funktiong = map(n*)
, die diese Funktion auf alle Elemente einer Liste anwendet, und füttert diese Funktion(=<<)(++)
. Hier(++)
ist die Verkettung Funktion und(=<<)
ist monadischen binden , die in diesem Fall nimmt(++)
undg
und gibt eine Funktion , die in einer Liste nimmt, giltg
zu einer Kopie davon, und verkettet die beiden.Kurz gesagt: Beginnen Sie mit
[1]
undn
kopieren Sie für jede Nummer in der Eingabeliste eine Kopie der aktuellen Liste, multiplizieren Sie alles mitn
und hängen Sie sie an die aktuelle Liste an.quelle
Python: 55 Zeichen
Generiert die Produkte rekursiv, indem Sie die einzelnen Nummern nacheinander ein- oder ausschließen.
quelle
and
wenn Sie die Summe umgekehrt schreiben?PARI / GP , 26 Bytes
Längere Versionen enthalten
(30 Bytes) und
(31 Bytes).
Wenn die Eingabe eine Faktorisierungsmatrix anstelle einer Menge wäre, könnten 18 Byte allein gespeichert werden
divisors
. Die Konvertierung einer Menge in eine Faktorisierungsmatrix scheint jedoch mehr als 18 Byte zu dauern. (Ich kann es in 39 Bytes direkt alsv->concat(Mat(v~),Mat(vectorv(#v,i,1)))
oder 24 Bytes durch Multiplikation und Re-Factoringv->factor(factorback(v))
tun, kann jemand es besser machen?)quelle
Salbei -
3634Im Wesentlichen die gleiche wie Martin Büttners Lösung , wenn ich es richtig verstehe. Wie ich es in einem Kommentar erwähnt habe, kann ich es auch als Antwort posten.
Dies ist eine anonyme Funktion, die beispielsweise folgendermaßen aufgerufen werden kann:
quelle
J (20)
Dies fiel länger aus als ich gehofft oder erwartet hatte. Trotzdem: kürzer als haskel!
Verwendung:
Dies funktioniert für jeden Satz von Zahlen, nicht nur für Primzahlen. Außerdem können die Primzahlen eine unbegrenzte Größe haben, solange das Array das Postfix hat
x
:2 3 5 7x
quelle
*/@#~2#:@i.@^#
ist eine Alternative für 14 Bytes.05AB1E , 2 Bytes
Probieren Sie es online!
Erläuterung
quelle
R, 56 Bytes
Ich überlege hier, dass s die Menge (und eine Liste) ist. Ich bin sicher, dass es noch kürzer gemacht werden kann. Ich werde sehen.
quelle
PHP, 97 Bytes
quelle