Aufgabe
Schreiben Sie eine Funktion, die zwei Ganzzahlen akzeptiert a,b
, die die Gaußsche Ganzzahl z = a+ib
(komplexe Zahl) darstellen. Das Programm muss true oder false zurückgeben, je nachdem, ob a+ib
es sich um eine Gaußsche Primzahl handelt oder nicht .
Definition:
a + bi
ist genau dann eine Gaußsche Primzahl, wenn sie eine der folgenden Bedingungen erfüllt:
a
undb
sind beide ungleich Null unda^2 + b^2
sind Primzahla
ist Null,|b|
ist Primzahl und|b| = 3 (mod 4)
b
ist Null,|a|
ist Primzahl und|a| = 3 (mod 4)
Einzelheiten
Sie sollten nur eine Funktion schreiben. Wenn Ihre Sprache keine Funktionen hat, können Sie davon ausgehen, dass die Ganzzahlen in zwei Variablen gespeichert sind und das Ergebnis drucken oder in eine Datei schreiben.
Sie können keine eingebauten Funktionen Ihrer Sprache wie isprime
oder prime_list
oder nthprime
oder verwenden factor
. Die niedrigste Anzahl von Bytes gewinnt. Das Programm muss Arbeit für , a,b
wo a^2+b^2
ein 32 - Bit (signiert) integer und sollte in nicht wesentlich mehr als 30 Sekunden beenden.
Prime-Liste
Die Punkte repräsentieren Primzahlen auf der Gaußschen Ebene ( x
= reelle, y
= imaginäre Achse):
Einige größere Primzahlen:
(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)
quelle
factor
in Bashmf
undmF
in CJam, ...)Antworten:
Haskell -
77/108107 ZeichenVerwendung: In beiden Lösungen gibt die Eingabe von a% b zurück, ob a + bi eine Gaußsche Primzahl ist.
das niedrigste, das ich geschafft habe, aber keine Kreativität oder Leistung (77 Zeichen)
Diese Lösung durchläuft nur alle Zahlen unter n, um zu prüfen, ob es sich um eine Primzahl handelt.
ungolfed version:
Die nächste Lösung hat eine zusätzliche Funktion - Memoization. Wenn Sie überprüft haben, ob eine Ganzzahl n eine Primzahl ist, müssen Sie die "Primzahl" aller Zahlen, die kleiner oder gleich n sind, nicht neu berechnen, da sie im Computer gespeichert werden.
(107 Zeichen. Die Kommentare dienen der Klarheit.)
ungolfed version:
Dabei wird das Sieb von Eratosthenes verwendet, um eine unendliche Liste aller Primzahlen zu berechnen (im Code als l für Liste bezeichnet). (Unendliche Listen sind ein bekannter Trick von Haskell).
Wie ist es möglich, eine unendliche Liste zu haben? Zu Beginn des Programms wird die Liste nicht ausgewertet. Statt die Listenelemente zu speichern, speichert der Computer die Berechnungsmethode. Wenn das Programm jedoch auf die Liste zugreift, wertet es sich teilweise selbst bis zur Anforderung aus. Wenn das Programm also das vierte Element in der Liste anfordert, berechnet der Computer alle Primzahlen bis zum vierten Element, die noch nicht ausgewertet wurden, speichert sie, und der Rest bleibt unbewertet und wird als Berechnungsmethode einmal gespeichert erforderlich.
Beachten Sie, dass all dies durch die Trägheit der Haskell-Sprache frei gegeben ist, nichts davon geht aus dem Code selbst hervor.
Beide Programmversionen sind überlastet, sodass sie Daten beliebiger Größe verarbeiten können.
quelle
C,
149118 ZeichenBearbeitete Version (118 Zeichen):
Dies ist eine einzelne Funktion:
Es faltet den ganzzahligen Primalitätstest in einen Ausdruck
n/d/d|n<2
, der in der Rückgabewertberechnung verborgen ist. Dieser Golf-Code wird aucha*b
als Ersatz füra&&b
(mit anderen Wortena!=0 && b!=0
) und andere Tricks verwendet, bei denen der Operator Vorrang hat und die Ganzzahlteilung eine Rolle spielt. Zum Beispieln/d/d
ist eine kürzere Art zu sagenn/d/d>=1
, die eine überlaufsichere Art zu sagen istn>=d*d
oderd*d<=n
oder im Wesentlichend<=sqrt(n)
.Originalfassung (149 Zeichen):
Funktionen:
Q ( n ) gibt 0 (falsch) zurück, wenn n eine Primzahl ist, oder 1 (wahr), wenn n keine Primzahl ist. Es ist eine Hilfsfunktion für G ( a , b ).
G ( a , b ) gibt 1 (wahr) zurück, wenn a + bi eine Gaußsche Primzahl ist, oder 0 (falsch), wenn dies nicht der Fall ist.
Beispielausgabe (200% vergrößert) für | a |, | b | ≤ 128:
quelle
d++
nicht als Teil der Bedingung geschieht, da es sonst die folgende Logik durcheinander bringt. Wenn Sie dasd=2
Innere derfor
Schleife verschieben, wird die Anzahl der Zeichen eher erhöht als verringert, da diesd
immer noch alsint
vor derfor
Schleife deklariert werden muss . Vermisse ich etwas?G(a,b){int s=abs(a)+abs(b),n=a*b?a*a+b*b:s,d=2;for(;n/d/d&&n%d;d++);return n>1>n/d/d&&s%4/3|a*b;}
ergibt nur 97 Zeichen.APL (Dyalog Unicode) ,
36474849474328 BytesNimmt ein Array mit zwei Ganzzahlen
a b
und gibt den Booleschen Wert der Anweisung zurücka+bi is a Gaussian integer
.Edit: +11 Bytes, weil ich die Definition einer Gaußschen Primzahl falsch verstanden habe. +1 Byte von der erneuten Korrektur der Antwort. +1 Byte von einer dritten Fehlerbehebung. -2 Bytes aufgrund der Verwendung eines Zuges anstelle eines DFN. -4 Bytes dank ngn aufgrund der Verwendung eines Guard
condition: if_true ⋄ if_false
anstelle vonif_true⊣⍣condition⊢if_false
. -15 Bytes dank ngn, da ein völlig anderer Weg gefunden wurde, um die Bedingung-if-else als vollen Zug zu schreiben.Probieren Sie es online!
Erläuterung
quelle
Haskell - 121 Zeichen (einschließlich Zeilenumbrüche)
Hier ist eine relativ einfache Haskell-Lösung, bei der keine externen Module verwendet werden und die so weit wie möglich heruntergespielt wird.
Aufrufen als
ghci ./gprimes.hs
und dann können Sie es in der interaktiven Shell verwenden. Hinweis: Negative Zahlen sind heikel und müssen in Klammern gesetzt werden. Dhquelle
Python -
121120 Zeichenp
Überprüft, obabs(x)
eine Primzahl vorliegt, indem alle Zahlen von 2 bisabs(x)**.5
(was istsqrt(abs(x))
) durchlaufen werden . Es tut dies, indem esx % s
für jeden nachgibts
.all
überprüft dann, ob alle ausgegebenen Werte ungleich Null sind, und beendet die Generierung von Werten, sobald ein Divisor von angetroffen wirdx
. Inf
,f(b,a)
ersetzt den Fall fürb==0
, inspiriert von @killmous 'Haskell Antwort.-1 char und Bugfix von @PeterTaylor
quelle
s<abs(x)**.5
mit ersetzens*s<abs(x)
. Obwohl Sie wirklich prüfen sollten<=
, so ist es wahrscheinlich zur Zeit fehlerhaft.f(0,15)
AusbeuteTypeError: unsupported operand type(s) for &: 'bool' and 'generator'
mit meinem Dolmetscher. :(f(0,15)
gibtFalse
für mich sowohl auf 2.7.6 als auch auf 3.4.1 (unter OS X). Auf welcher Version bist du?Python 2.7 ,
341301253 Bytes, optimiert für GeschwindigkeitProbieren Sie es online!
Danke: 40 +48 - ganzes Golfen an Jo King
quelle
f
Lambda ist auch nicht notwendig, zusammen mit demlist
Anruf. 257 Bytes ohne diese, plus einige Leerzeichenentfernung. Das ist vielleicht nicht mehr so effizientPerl -
110107105 ZeichenIch hoffe, ich habe die verknüpfte Definition korrekt befolgt ...
Ungolfed:
Erklärung, weil jemand gefragt: ich die Argumente lesen (
@_
) und setzen ihre absoluten Werte in$a
,$b
, weil die Funktion braucht nicht ihre Zeichen. Für jedes Kriterium muss die Primalität einer Zahl getestet werden. Diese Zahl hängt jedoch davon ab, ob sie Null ist$a
oder nicht.$b
Ich habe versucht, sie auf kürzestem Weg auszudrücken und sie einzugeben$n
. Schließlich überprüfe ich, ob$n
Primzahl ist, indem ich zähle, wie viele Zahlen zwischen 2 und sich selbst ohne Rest teilen (das ist dergrep...<2
Teil), und prüfe dann zusätzlich, dass, wenn eine der Zahlen Null ist, die andere 3 Modulo 4 entspricht. Die Funktion ist Rückgabewert ist standardmäßig der Wert der letzten Zeile, und diese Bedingungen geben einen Wahrheitswert zurück, wenn alle Bedingungen erfüllt sind.quelle
$a%4>2
anstatt$a%4==3
.Golflua
147141Die obige Anzahl vernachlässigt die Zeilenumbrüche, die ich hinzugefügt habe, um die verschiedenen Funktionen zu sehen. Trotz des Bestehens, dies nicht zu tun, löse ich Primzahlen mit brachialer Gewalt in den Fällen.
Gibt 1 zurück, wenn wahr, und 0, wenn nicht.
Eine ungolfed Lua Version,
quelle
tonumber(io.read())
als Argumentg
einfügen, und 2 weitere, indem Sie die Zeilenumbrüche entfernena
wo ,|a| <= |z|
wenna | z
(fallsa
dividierenz
).APL (NARS), 99 Zeichen, 198 Byte
Prüfung:
quelle
Runenverzauberungen , 41 Bytes
Probieren Sie es online!
Am Ende war es viel einfacher als ich dachte und es gab nicht viel Raum für Golf. Das ursprüngliche Programm, das ich gesperrt habe, war:
Ich habe versucht, beide Eingänge gleichzeitig zu vergleichen (was alles von einem Byte sparte), aber wenn das in den Abschnitt "einer von ihnen ist Null" fällt, gab es keinen guten Weg, um herauszufinden, welches Element war ungleich Null, um die letzte Prüfung durchzuführen, geschweige denn eine Möglichkeit, dies zu tun, ohne mindestens 1 Byte auszugeben (keine Gesamteinsparung).
quelle
Mathematica, 149 Zeichen
Der Code verwendet keine Standardmerkmale für Primzahlen in Mathematica, sondern zählt die Anzahl der Ganzzahlen in der Liste {n / 1, n / 2, ..., n / n}. Wenn die Zahl 1 oder 2 ist, ist n eine Primzahl. Eine ausgearbeitete Form der Funktion:
Bonusplot aller Gaußschen Primzahlen von -20 bis 20:
quelle
Ruby
-rprime
,656080 BytesDie Regel "isPrime kann nicht verwendet werden" wurde nicht beachtet ...
Probieren Sie es online!
quelle
Python -
117 122121quelle
==3
mit>2