Der "Prime Frog" ist ein seltsames Tier, das zwischen ganzen Zahlen springt, bis es am 3. oder 19. ...
Ihr Programm sollte eine Ganzzahl n
als Eingabe akzeptieren und das Ergebnis des folgenden Algorithmus ( 3
oder 19
) ausgeben .
Für eine bestimmte Ganzzahl n >= 2
:
- Sei
f
die Position des Frosches. Es ist anfänglich auf eingestelltn
- wenn
f = 3
oderf = 19
: der Frosch springt nicht mehr - stoppen Sie das Programm und geben Sie es ausf
. - wenn
f
ist prime: der frosch springt zur position2×f-1
. Fahren Sie mit Schritt 2 fort. - if
f
ist zusammengesetzt: seid
derf
größte Primteiler. Der Frosch springt auf die Positionf-d
. Fahren Sie mit Schritt 2 fort.
Beispiele:
Ein Beispiel mit n = 5
:
5 > 9 > 6 > 3 stop
Das Programm sollte ausgeben 3
.
Ein weiteres Beispiel mit n = 23
:
23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop
Auch hier sollte das Programm ausgeben 3
.
Testfälle:
10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19
Sie können davon ausgehen 1 < n < 1000000
(ich habe das Programmende auf diese Werte überprüft).
3
oder kommt19
, können wir Punkt 2 im Algorithmus ändern, um zu sagen, dass, wenn der Frosch in eine Schleife eingetreten ist (auf eine Position gestoßen ist, die er zuvor gesehen hat), er das Springen beendet und die kleinste zurückgibt Mitglied dieser Schleife.Antworten:
Python 2 ,
101939290888785 BytesProbieren Sie es online!
quelle
while~16&n!=3
Speichert ein Byte.~16&n-3
sogar funktioniert!C (gcc)
8765 BytesProbieren Sie es online!
Erläuterung:
Portable Version (72 Bytes):
Probieren Sie es online!
Mit passenderen Variablennamen:
Probieren Sie es online!
quelle
Retina ,
6362 BytesVielen Dank an Neil für das Speichern von 1 Byte.
Probieren Sie es online!
Ein- und Ausgabe in Unary (die Testsuite verwendet aus Bequemlichkeitsgründen Dezimalzahlen). Diese Lösung wird für größere Eingaben unglaublich langsam. Der
9983
Testfall läuft bei TIO ab.Erläuterung
Aufgrund dessen
{
werden beide Programmphasen einfach in einer Schleife abgearbeitet, bis sie den String nicht mehr beeinflussen. Wir wechseln zwischen einem Stage Processing Composites und einem Stage Processing Primes. Auf diese Weise können wir eine tatsächliche Bedingung vermeiden (die in der Netzhaut nicht wirklich existiert). Wenn der aktuelle Wert für die Bühne falsch ist, tut die Bühne einfach nichts.Dies verarbeitet Verbundstoffe. Wir stimmen einen potenziellen Divisor mit ab
(11+)
, prüfen dann aber, ob er nicht mit zusammengesetzt ist(?<!^\2+(11+))
, und berücksichtigen daher nur Primfaktoren. Aufgrund der Gier von+
, priorisieren diese den größten Faktor. Dann überprüfen wir, ob dieser potentielle Teiler ein tatsächlicher Teiler ist, indem wir versuchen, den Rest der Zeichenkette mit Wiederholungen davon abzugleichen(?=\1+$)
. Dieser Teiler wird einfach aus der Zeichenkette entfernt, wodurch Sie etwas in unary subtrahieren.Dies verarbeitet Primzahlen mit Ausnahme von 3 und 19 . Der negative Lookahead stellt sicher, dass die Eingabe nicht zusammengesetzt ist, nicht 3 und nicht 19 . Dann passen wir eine einzelne an
1
und ersetzen sie durch die gesamte Zeichenfolge. Dies ist eine unäre Form der Berechnung von n - 1 + n , die natürlich 2n-1 ist .Sobald wir 3 oder 19 erreicht haben , kann keine der Stufen mit der Saite übereinstimmen und sie wird nicht mehr geändert.
quelle
1$'
dasselbe wie$_
?Schale , 15 Bytes
Probieren Sie es online!
Erläuterung
quelle
Gelee , 12 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Wolfram Language (Mathematica) , 65
6668BytesProbieren Sie es online!
Inspiriert von der Spitze . Grundsätzlich wird nur der Algorithmus neu erstellt.
//.
istRepeatedReplace
und/;
istCondition
. Der Code wird also durchi_
(eine einzelne Menge) ersetztIf[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]
, bis eri!=3&&!=19
ausgewertet wirdTrue
.Benchmark:
quelle
10000000010
damaximum number of iterations is 2^16 (= 65536)
#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
05AB1E ,
191817 BytesProbieren Sie es online!
Erläuterung
quelle
<ë
JavaScript (ES6),
737169 BytesTestfälle
Code-Snippet anzeigen
Formatiert und kommentiert
quelle
57%n
undn%38
stattn==3|n==19
. 1 Byte in meiner Java-Antwort auch gespeichert , also danke!Jelly ,
2319 Bytes-4 Bytes von Meilen . Immer noch länger als 05AB1E.
Probieren Sie es online!
quelle
Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿
Verwenden Sie stattdessen eine while-Schleife und einige NachbestellungenPython 2 ,
110105103101 Bytes-2 Bytes dank @Lynn
Probieren Sie es online!
Python 2 ,
116112105 BytesProbieren Sie es online!
quelle
…n*(n&~16==3)or…
Spart 2 Bytes.MATL ,
2221 BytesVielen Dank an @ Giuseppe für das Entfernen von 1 Byte!
Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Erläuterung
quelle
Haskell - 154 Bytes
Vermutlich fehlen hier einige Golf-Tricks, dies ist mein erster Versuch, Haskell Golf zu spielen.
quelle
1>0
für dieTrue
meiste Zeit aber oft ist es vielleicht besser sein , um eine Zuordnung zu verwenden, zum Beispielc<-z n
.[x|x<-[b-1,b-2..1],rem b x==0]
ist auch kurz alsreverse[x|x<-[1..(b-1)],b
remx==0]
.Neim ,
1716 BytesErläuterung:
Probieren Sie es online!
quelle
R + Nummern ,
102 bis99 BytesProbieren Sie es online!
R ist nicht für kurze Einbauten bekannt, und sogar die Pakete folgen diesem Beispiel!
quelle
Java 8,
14013513494 Bytes-5 Bytes bei der Konvertierung der rekursiven Java 7-Methode in Java 8-Lambda mit Schleife.
-1 Byte implizit dank der JavaScript-Antwort von @Arnauld durch Ändern von
n!=3&n!=19
undreturn n;
nach57%n>0
undreturn n%38;
.Ich denke, es sollte irgendwie möglich sein, die beiden Schleifen zu kombinieren und zu prüfen, obn
es sich um eine Primzahl handelt, und gleichzeitig den größten Primfaktor zu erhalten, aber ich kann es (noch) nicht herausfinden. Dies wird also die erste Version für den Moment sein.-40 satte Bytes dank @Nevay, indem ich das tue, was ich nicht konnte: die Schleifen kombinieren, um sofort nach Primzahlen und dem größten Primfaktor zu suchen.
Erläuterung:
Probieren Sie es hier aus (wird sogar
999999
in weniger als 1 Sekunde ausgeführt).quelle
n=>
stattn->
. Und manchmal Klein- / Großbuchstaben. ;)n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;)t/=m=f;return n%38;}
Bash, 73 Bytes
Probieren Sie es online! Leicht modifiziert, um mit TIO zu arbeiten.
Ruft rekursiv eine eigene Skriptdatei mit auf
$0
,die in TIO nicht funktioniert, da sie als ausgeführt werden muss. Akzeptiert Eingaben als Befehlszeilenargument../filename.sh
Verwendet den gleichen Modulus-Trick wie die JS-Antwort von @ Arnauld .
Testfälle
quelle
Python 3 , 97 Bytes
Probieren Sie es online!
quelle
Pyth , 19 Bytes
Überprüfen Sie alle Testfälle!
Die Antwort von Husk hat mich dazu inspiriert, 2 Bytes (
,3 19
bisP57
) zu sparen .Wie das geht
quelle
PowerShell ,
150 bis126 ByteProbieren Sie es online! (Warnung: langsam für größere Zahlen)
Iterative Methode. PowerShell verfügt über keine eingebauten Primfaktor-Funktionen. Daher ist dieser Code aus meiner Antwort auf Prime Factors Buddies entlehnt .
Erstens ist unsere
for
Schleife. Das Setup wird$n
als Eingabewert festgelegt, und die Bedingung hält die Schleife so lange aufrecht, wie sie57%$n
nicht Null ist (danke an Arnauld für diesen Trick). Innerhalb der Schleife erhalten wir zunächst eine Liste der Primfaktoren von$a
(set to$n
). Dies ist der Code, der von Prime Factors Buddies entlehnt wurde. Wenn der Eingang$a
bereits prim ist, wird dies nur zurückgegeben$a
(wichtig später). Das wird (möglicherweise nur$a
) in gespeichert$d
.Weiter ist ein
if
/else
bedingt. Zumif
Teil prüfen wir, ob das so$n
ist-in
$d
. Wenn es so ist, heißt das, dass$n
es prim ist, also nehmen wir$n=2*$n-1
oder$n+=$n-1
. Ansonsten ist es zusammengesetzt, also müssen wir den größten Primfaktor finden. Das heißt, wir müssen den letzten[-1]
von nehmen$d
und diesen von$n
mit subtrahieren$n-=
. Dies funktioniert, weil wir eine Schleife ablaufen2
und somit das letzte Element von$d
bereits das größte ist.Sobald wir mit dem Looping fertig sind, platzieren wir
$n%38
(nochmals danke Arnauld) in der Pipeline und die Ausgabe ist implizit.quelle
APL (Dyalog Unicode) ,
1139059 BytesProbieren Sie es online!
TIO arbeitet mit Werten bis zu ~ 3200. Auf meinem PC für den letzten Testfall getestet. Fügen Sie zum Testen von TIO einfachGilt nicht mehr, danke an @ Adám, der darauf hingewiesen hat, dass mein Algorithmus für die Primalitätsprüfung wirklich schlecht war, und der mir Ersatz geliefert hat. auch für die 23 byte speichern.f value
am Ende des Codes hinzu.Bearbeitet, um die Anzahl der Bytes zu korrigieren.
Wie es funktioniert
quelle
Axiom 93 Bytes
Prüfung:
Es würde 68 Bytes Funktion geben
aber für n = 57991 (wenn ich mich recht erinnere) geht der reservierte Stapelplatz raus.
quelle
Python 2 , 93 Bytes
Port von TFelds Antwort ohne externe Bibliotheken.
Probieren Sie es online!
quelle