Eine stark zusammengesetzte Zahl ist eine positive Ganzzahl mit mehr Teilern als jede kleinere positive Ganzzahl. Dies ist die OEIS-Sequenz A002182 . Seine ersten 20 Amtszeiten sind
1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560
Zum Beispiel 4
ist in der Sequenz, weil es 3 Teiler hat (nämlich 1, 2, 4), während 3 nur 2 Teiler hat, 2 auch 2 Teiler hat und 1 1 Teiler hat.
Herausforderung
Bei einer positiven Ganzzahleingabe n geben Sie nach Ihrer Wahl entweder die n- te zusammengesetzte Zahl oder die ersten n zusammengesetzten Zahlen aus (die Auswahl muss jedoch für jede Eingabe n gleich sein ).
Regeln
Das Programm oder die Funktion sollte theoretisch für beliebig große Eingaben bei unbegrenzter Zeit und unbegrenztem Arbeitsspeicher und ohne Berücksichtigung von Datentypbeschränkungen funktionieren. Im Wesentlichen bedeutet dies, dass eine endliche Anzahl von Werten nicht hartcodiert werden muss.
In der Praxis sollte das Programm oder die Funktion in einer angemessenen Zeitspanne, beispielsweise weniger als 1 Minute, für n bis 20 ausgeführt werden. Die maximale Eingabe oder Ausgabe kann durch den Standarddatentyp Ihrer Sprache begrenzt sein (der Algorithmus sollte jedoch theoretisch funktionieren für beliebig große Zahlen).
Jedes sinnvolle Eingabe- und Ausgabeformat ist zulässig, auch unary.
Code Golf. Wenigste Bytes gewinnt.
quelle
Antworten:
05AB1E ,
1514 BytesDie Eingabe ist nullindexiert. Das heißt, dass
n = 0
gibt1
,n = 1
gibt2
, etc. Code:Erläuterung:
Berechnet n = 19 , was
7560
in ungefähr 10 Sekunden ergeben sollte.Probieren Sie es online!
Verwendet CP-1252- Codierung.
quelle
Gelee, 15 Bytes
Bei Eingabe von n werden die ersten n zusammengesetzten Zahlen ausgegeben.
Bei n = 20 dauert es weniger als zwei Sekunden. Online testen!
Wie es funktioniert
Alternative Version, 13 Bytes (nicht konkurrierend)
Während der unten stehende Code in der neuesten Version von Jelly, die dieser Herausforderung vorausgeht, funktioniert hat, war die Implementierung von
M
sehr langsam und hat das Zeitlimit nicht eingehalten. Dies wurde behoben.Probieren Sie es online!
Wie es funktioniert
quelle
RÆDL€MḢ=µƓ#
(11 Bytes), aber es dauert 44 Minuten auf meinem Computer ...MATL ,
2624 BytesProbieren Sie es online!
Die aktuell größte Anzahl der gefundenen Teiler befindet sich in der Zwischenablage K. Hochkompositzahlen (HCN) werden direkt auf dem Stapel abgelegt. In einer Schleife werden weiterhin Kandidaten für HCN getestet. Wenn eines gefunden wird, bleibt es auf dem Stapel und die Zwischenablage K wird aktualisiert. Die Schleife wird beendet, wenn die gewünschte Anzahl von HCN gefunden wurde.
quelle
Perl,
6057 + 1 = 58 BytesBenötigt
-n
und die freie-M5.010
|-E
:Wie es funktioniert:
quelle
JavaScript (ES6) 72
Einfache Implementierung. Zeit nahe 20 Sekunden für Eingang 20
Durch den Auswertungs-Trick könnte ein Byte eingespart werden, das die Laufzeit verdoppelt
Weniger golfen
quelle
Pyth,
1716 Bytes1 Byte danke an Jakube
Testsuite
Nimmt ein 0-indiziertes n und gibt die n-te zusammengesetzte Zahl zurück.
Erläuterung:
quelle
Ruby,
706967666462Einfache Implementierung.
quelle
C 98 Bytes
Versuch es hier aus .
Ungolfed
quelle
Python 3, 97 Bytes
Ein vollständiges Programm, das Eingaben von STDIN entgegennimmt und die Ausgabe an STDOUT ausgibt. Dies gibt die
n
th 1-indexierte hoch zusammengesetzte Zahl zurück.Wie es funktioniert
Dies ist eine einfache Implementierung. Die Eingabe
n
ist der stark zusammengesetzte Zahlenindex.Das Programm durchläuft die ganzen Zahlen
i
. Für jede ganze Zahl wirdj
kleiner alsi
,i mod j
genommen; Wenn dies der Fall ist0
,j
muss dies ein Faktor von sein,i
und der Zählerc
wird inkrementiert, wobei die Anzahl der Teileri
nach der Schleifenbildung angegeben wird.p
ist die bisher höchste Anzahl von Teilern. Wenn alsoc > p
eine neue, stark zusammengesetzte Zahl gefunden wurde, wird der Zählerq
inkrementiert. Einmalq = n
,i
muss dien
th hoch zusammengesetzte Zahl, und diese gedruckt werden.Probieren Sie es auf Ideone
(Dies dauert ca. 15 Sekunden
n = 20
und überschreitet damit das Zeitlimit für Ideone. Daher gilt das angegebene Beispiel fürn = 18
.)quelle
Python 2, 207 Bytes
Verwendet die gleiche Methode wie Dennis 'Jelly-Antwort. Berechnet die ersten 20 Terme in
<2
Sekunden.quelle