Von all den Jahren, in denen ich diese Herausforderung gemeistert habe, war 2017 das erste Jahr, das eine Primzahl war. Die Frage wird also nach Primzahlen und ihren Eigenschaften sein.
Ihre Aufgabe ist es, ein Programm oder eine Funktion zu erstellen, die eine willkürlich große positive Ganzzahl als Eingabe verwendet und ausgibt oder zurückgibt, ob die Zahl 2.017-brüchig ist oder nicht, dh ob der größte Primfaktor in dieser Zahl 2.017 oder weniger ist.
Einige Beispieleingaben und ihre Ausgaben:
1 (has no prime factors)
true
2 (= 2)
true
80 (= 2 x 2 x 2 x 2 x 5)
true
2017 (= 2017)
true
2019 (= 3 x 673)
true
2027 (= 2027)
false
11111 (= 41 x 271)
true
45183 (= 3 x 15061)
false
102349 (= 13 x 7873)
false
999999 (= 3 x 3 x 3 x 7 x 11 x 13 x 37)
true
1234567 (= 127 x 9721)
false
4068289 (= 2017 x 2017)
true
Ihr Programm muss nicht buchstäblich true
und false
- irgendwelche wahren oder falschen Werte ausgeben, und tatsächlich sind zwei verschiedene Ausgaben, die über wahre und falsche Fälle hinweg konsistent sind, in Ordnung.
Sie dürfen jedoch keine Primzahlen in Ihrem Quellcode verwenden. Es gibt zwei Arten von Primzahlen:
Zeichen oder Zeichenfolgen, die Primzahlliterale darstellen.
Die Zeichen
2
,3
,5
, und7
sind illegal in Sprachen , in denen Zahlen gelten Token.Die Nummer
141
ist illegal, weil sie enthält41
, obwohl1
und4
sonst gültig sind.Die Zeichen
B
undD
(oderb
undd
) sind in Sprachen, in denen sie normalerweise als 11 und 13 verwendet werden, wie z. B. CJam oder Befunge, illegal.
Zeichen, die Unicode-Werte mit dem höchsten Wert haben oder in ihrer Codierung Bytes mit dem höchsten Wert enthalten.
Die Zeichen
%)+/5;=CGIOSYaegkmq
sind in ASCII unzulässig, ebenso wie das Wagenrücklaufzeichen.Das Zeichen
ó
ist in UTF-8 unzulässig, da die Codierung darin enthalten ist0xb3
. In ISO-8859-1 ist die Codierung jedoch einfach0xf3
, was zusammengesetzt ist und daher in Ordnung ist.
Der kürzeste Code, der in einer beliebigen Sprache für die oben genannten Aufgaben verwendet wird, gewinnt.
=
schließt die meisten Standardsprachen aus ...Antworten:
Gelee , 8 Bytes
Probieren Sie es online! Beachten Sie, dass die Testfälle 11111 und höher für TIO etwas zu viel sind.
Nachprüfung
Der Testfall 999999 wurde 13 Stunden lang ausgeführt. Ich bin pessimistisch in Bezug auf das Rechnen 2025! 4068289 ...
Wie es funktioniert
quelle
(2^n)!
. Dies gilt auch für Eingaben in sechs Größen, aber zumindest sind die Eingaben in einem Dezimalalphabet und nicht in einem Binäralphabet.Jelly , 8 Zeichen, 14 Byte UTF-8
Probieren Sie es online!
Jelly verwendet normalerweise eine eigene Codepage für Programme. Die meisten seiner primitiven Buildins beginnen jedoch mit
Æ
Codepoint 13; nicht sehr hilfreich. Glücklicherweise unterstützt der Interpreter auch UTF-8, das eine freundlichere Codierung aufweist.Nachprüfung
Dieses Programm erstellt in UTF-8 Hexdumps wie folgt:
Überprüfung, dass alle Bytes zusammengesetzt sind:
Überprüfung, dass alle Unicode-Codepunkte zusammengesetzt sind:
Das einzige als Zahl analysierte Token ist
90
. Nichts von9
,0
und90
sind Primzahl.Erläuterung
Die wichtigste mathematische Erkenntnis hier ist, dass 45² 2025 ist, was genau zwischen 2017 (das aktuelle Jahr) und 2027 (die nächste Primzahl) liegt. Wir können also die Quadratwurzel jedes Primfaktors der Zahl ziehen und sehen, ob einer größer als 45 ist. Leider können wir
45
aufgrund des Literal nicht schreiben5
, also müssen wir ihn verdoppeln und stattdessen mit 90 vergleichen.quelle
u
zusammengesetzt, es geht also nur darum, die Punktzahl zu ändern und nicht um etwas, das sie ungültig macht.)Mathematica,
625855 BytesDie letzten drei Bytes, die gespeichert wurden, sind Martin Ender zu verdanken!
Unbenannte Funktion, die ein positives ganzzahliges Argument verwendet und
True
oder zurückgibtFalse
.Rekursiver Algorithmus,
#4<4
der der wahre Basisfall ist (wir brauchen ihn nur, umTrue
auf den Eingang 1 zurückzukehren, aber die zusätzlichen Basisfälle sind in Ordnung). Ansonsten berechnen wir den zweitkleinsten Divisor (der notwendigerweise Primzahl ist) der Eingabe mitDivisors[#][[6-4]]
; Wenn es größer als 2024 (44*46
) ist, beenden wir mitFalse
, andernfalls rufen wir die Funktion rekursiv (mit#6
set to#0
) für die Eingabe dividiert durch diesen kleinen Primfaktor auf#
(den wir als#^-1
Zeiten der Eingabe ausdrücken müssen#4
, da dies/
nicht zulässig ist).Strukturell die erste Hälfte
#4<4||#<44*46&[#^-1#4]&
ist eine anonyme Funktion der sechs Argumente, mit Argumenten aufgerufen wirdDivisors[#][[6-4]]
,Null
,Null
,#
,Null
, und#0
; Dies soll das Verbot der Charaktere2
umgehen3
, und5
.Vorherige Version, die durch Ersetzen vier Bytes gespeichert
8018-6000
mit44*46
, inspiriert von ais523 Gelee Antwort (Martin Ender schien auch von einem ais523 Kommentar inspiriert):Das war ziemlich unangenehm: Ich weiß immer noch nicht, wie ich eine Variable in Mathematica unter diesen Einschränkungen setzen kann! Sowohl
=
und diee
inSet
sind nicht zulässig. Vermeiden+
und)
war auch ein Problem, aber nicht zu schwer zu umgehen auf Kosten von mehr Bytes.quelle
#2
wäre auch nicht erlaubt, so dass Sie vorsichtig sein müssten, wie Ihre Lambdas verschachtelt sind, und das Fehlen von Klammern könnte dies schwierig machen.)#4<4||#<44*46&[#^-1#4]&[Divisors[#][[6-4]],,,#,,#0]&
eine Reihe von Warnungen ausgegeben, da jetzt versucht wird,Divisors[#][[2]]
sicherzustellen, dass die Eingabe größer als 1 (oder 3) ist, das Ergebnis jedoch weiterhin korrekt ist.Haskell,
4847 BytesGrundsätzlich eine Übersetzung von Dennis 'Jelly Antwort . xnor hat ein Byte gespeichert.
Wird
[…]!!0
als Klammer verwendet, weil)
gesperrt ist undsnd
+,divMod
weilm
inmod
undrem
gesperrt ist.quelle
!!0<1
mit ersetzen<[1]
. Aber es sieht es , es zu benutzen kurzgeschlossen ist ,div
wie[\p n->p^n`div`n*n>p^n-1]!!0$product[1..44*46]
.\n->[0|p<-[product[1..44*46]^n],0<-[p,p-n..0]]
Verwendungen, bei denen Ausgaben nur konsistent sein müssen.Pyke,
10879 BytesProbieren Sie es hier aus!
1 Byte mit Dennis 'Methode zur Generierung von 2025 eingespart
quelle
Brachylog ,
910 BytesProbieren Sie es online!
Grundsätzlich mit dem gleichen Algorithmus wie meine andere Antwort.
$ph
findet den ersten (h
) Primfaktor ($p
); Dies ist der größte Primfaktor, da Brachylogs Primfaktorlisten vom größten zum kleinsten gehen. Dann nehme ich die Quadratwurzel ($r
), double (*
) und teste, ob es weniger als 90 ist (<90
).Ich musste zuerst die Eingabe verdoppeln, weil 1 keine Primfaktoren (und damit keinen ersten Primfaktor) hat. Dies fügt einen zusätzlichen Primfaktor von 2 hinzu, der keinen Einfluss darauf hat, ob eine Zahl 2017 brüchig ist, aber einen Fehler bei der Behandlung von 1 verhindert.
quelle
Eigentlich 9 Bytes
Danke an Dennis für die vielen Bytes!
Probieren Sie es online!
Erläuterung:
quelle
Mathematica,
6674 BytesVielen Dank an Dennis für den Hinweis, dass dies
U+F4A1
verboten ist.Erläuterung:
Divisors@#
: Liste der ganzzahligen Teiler des ersten Arguments#
.0<1
: Golf fürTrue
(vermeidet auch die Verwendung des Buchstabense
).Divisors@d^0
: Liste des Formulars{1, 1, ..., 1}
mit der Länge gleich der Anzahl der Teiler vond
.Tr
: Gibt für eine flache ListeTr
die Summe dieser Liste zurück. SoTr[Divisors@d^0]
gibt die Anzahl der Teiler vond
.Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]]
: Anonyme Funktion mit zwei Argumentenx
undd
. Die Idee ist, dass diesd
ein Teiler von ist#
und wir testen, ob es entweder zusammengesetzt oder kleiner oder gleich2017
(einschließlich) ist.2017
-Die Brüchigkeit entspricht allen Teilern, die diese Bedingung erfüllen. Wie ais523 herausgefunden hat , ist Primzahl kleiner oder gleich2017
Primzahl kleiner als2025
. Wie Greg Martin betonte, reicht es aus, zu testen, ob es weniger ist als2024=44*46
. Das Argumentx
dient als Akkumulator dafür, ob alle bisher angetroffenen Divisoren diese Eigenschaft erfüllen.Fold
Diese Funktion haben wir dann durch alle Teiler von#
mit Startwert verlassenTrue
, da wir weder Zugang habenMap
noch/@
.quelle
05AB1E , 10 Bytes
Gibt 1 zurück, wenn wahr, andernfalls 0.
Probieren Sie es online!
Erläuterung
quelle
MATL , 15 Bytes
Ausgänge
0
für Nicht-2017-Bröckelig oder1
für 2017-Bröckelig.Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Dieses Programm prüft, ob alle Bytes zusammengesetzt sind.
Erläuterung
quelle
Bash, 144 Bytes
ASCII-Codierung:
Wie bei Shell üblich, zeigt der Exit-Code Erfolg (0) oder Misserfolg (nicht 0) an.
Dies ist effektiv eine andere Schreibweise von
Wir bekommen den größten Faktor mit
factor $1|grep -o '[0-9]*$'
; Dastr -d :
ist zu Sonderfall für Eingabe =1
.Der Ausdruck wird
$[6*6*69-466]
bis 2018 ausgewertet.Es war schwierig,
tr
die Befehlsnamen zu verwenden und trotzdem die Befehlssubstitution zu verwenden. Ich konnte die Verschachtelungsform nicht verwenden$( )
, also leitete ich das Ergebnis in eine andere Bash um.Testergebnisse:
Bestätigung der Zeichencodes:
quelle
Pyth, 11 Bytes
Probieren Sie es online aus. Testsuite.
Verwendet Dennis 'Trick , um 2025 zu erhalten, und prüft dann, ob keine Primfaktoren der Eingabe größer sind.
quelle
Julia 0,4 ,
843837 BytesErwartet ein BigInt als Argument.
Probieren Sie es online! oder stellen Sie sicher, dass kein Byte prim ist .
quelle
Japt , 14 Bytes
Gibt 1 zurück, wenn wahr, 0, wenn falsch.
Probieren Sie es hier aus .
quelle
k
hat einen PrimwertBraingolf , 11 Bytes [sehr nicht konkurrierend]
Probieren Sie es online!
Unleserlich wegen der
ߢ
welche Schrauben mit den Nummern, funktioniert aber noch in einem Interpreter.Ich habe die Zeichenbeschränkungen nicht einmal bemerkt, als ich das geschrieben habe, aber alles, was ich tun musste, war, das seltsame Unicode-Zeichen von 2017 auf 2018 zu ändern.
Da 2018 keine Primzahl
<= 2018
ist , ist auch keine Primzahl<= 2017
Erläuterung
quelle