Einführung
Eisenstein-Ganzzahlen sind komplexe Zahlen der Form
a+bω
Wo a,b
sind ganze Zahlen und
ω = e^(2πi/3)
Die Eisenstein-Ganzzahlen bilden in der komplexen Ebene ein Dreiecksgitter:
Wir sagen, dass eine Eisenstein-Ganzzahl z=a+bω
eine Primzahl ist, wenn sie nicht als Produkt zweier Eisenstein-Ganzzahlen ohne Einheit (nicht 1, -1, ω, -ω, ω ^ 2 oder -ω ^ 2) geschrieben werden kann
Programm
Eingabe : Eine natürliche Zahl n
.
Ausgabe : Die Anzahl der Eisenstein-Primzahlen in der Form, a+bω
für die a,b
natürliche Zahlen (einschließlich Null) kleiner oder gleich sindn
Testfälle
0 → 0
1 → 0
2 → 5
3 → 9
4 → 13
5 → 20
Wertung
Dies bedeutet code-golf
, dass die geringste Anzahl von Bytes gewinnt
code-golf
primes
hexagonal-grid
complex-numbers
Miau Mix
quelle
quelle
a,b
Paare für2
ist nur4
so, wie könnte5
von ihnen Primzahl sein?Antworten:
Gelee, 24 Bytes
Etwa der gleiche Ansatz wie meine Antwort von Julia.
quelle
Julia,
666260 BytesProbieren Sie es online aus!
Erläuterung
Wir interessieren uns für die Primzahlen in diesem Parallelogramm auf der komplexen Ebene (Beispiel für n = 4 ):
Wir können sie in Primzahlen auf den grünen Linien und auf den grauen Linien aufteilen .
Wikipedia sagt mir, dass eine Eisenstein-Zahl z eine grüne Linie ist. Eisenstein prime iff | z | ist eine natürliche Primzahl gleich 2 mod 3.
Es heißt auch, dass z eine graue Linie ist. Eisenstein-Primzahl, wenn | z | ² = a² - ab + b² eine natürliche Primzahl ist.
Also durchlaufen wir a = 0… n und b = 0… n und prüfen:
Wenn (a = 0 oder b = 0 oder a = b) und max (a, b)% 3 = 2 , dann zähle, ob max (a, b) eine Primzahl ist.
Andernfalls zählen Sie, ob a² - ab + b² eine Primzahl ist.
Wir können jedoch die Symmetrie der Distribution missbrauchen. Anstatt jede grüne Linie einmal zu zählen, können wir nur dreimal eine grüne Linie zählen! Das heißt, überprüfen Sie a = 0 nur und erhöhen Sie den Zähler um drei, wenn wir eine grüne Primzahl finden. Das
a=[0;0;0:n]
erreicht genau das.Da wir wissen, dass wir nur die grüne Linie a = 0 berücksichtigen , können wir max (a, b) durch b ersetzen .
Die „Bedingung der grünen Linie“ wird in Julia durch die Verkettung von Operatoren gut ausgedrückt :
a<1<b%3
.(Für die verbleibenden grünen Linien werden wir niemals ein falsches Positiv zurückgeben: Wenn a = b oder b = 0, dann ist a² - ab + b² = a² , was keine Primzahl sein kann.)
Ideen
Vielleicht, statt zu schreiben
a^2-a*b+b^2
, kann ich bedingt den Exponenten ersetzen beib
durch ,1
wenna<1<b%3
- dann ist der Ausdruck reduziert sich aufb
. Das scheint nicht kürzer zu sein, aber es ist ordentlich!quelle
CJam (34 Bytes)
Online-Demo
quelle