is_gaussian_prime (z)?

23

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+ibes 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:

  • aund bsind beide ungleich Null und a^2 + b^2sind Primzahl
  • aist Null, |b|ist Primzahl und|b| = 3 (mod 4)
  • bist 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 isprimeoder prime_listoder nthprimeoder verwenden factor. Die niedrigste Anzahl von Bytes gewinnt. Das Programm muss Arbeit für , a,bwo a^2+b^2ein 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):

Bildbeschreibung hier eingeben

Einige größere Primzahlen:

(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)
fehlerhaft
quelle
2
Dürfen wir Faktorisierungsfunktionen verwenden ( factorin Bash mfund mFin CJam, ...)
Oh nein, ich habe vergessen, dass diese Faktorisierungsmethoden existieren, nein, bitte nicht =) Und die 32-Bit-Grenze gilt für a ^ 2 + b ^ 2, würde sonst keinen Sinn ergeben. Vielen Dank für Ihre Beiträge! Ich habe die Frage aktualisiert.
Fehler
2
Ich habe dem Beitrag eine Definition von Gaußschen Primzahlen hinzugefügt. Wenn Sie nicht mögen, wie ich es gemacht habe, können Sie es zurücksetzen, aber ich würde definitiv empfehlen, die Definition irgendwo aufzunehmen.
Undergroundmonorail
Das ist schön, ich wollte ursprünglich nur nicht direkt darauf hinweisen, wie man die Ursprünglichkeit bestimmt, damit die Menschen kreativ werden =)
Fehler
1 1073741857 scheint mir keine Gaußsche Primzahl zu sein, weil 1 ^ 2 + 1073741857 ^ 2 eine gerade Zahl ist ...
RosLuP

Antworten:

4

Haskell - 77/108 107 Zeichen

Verwendung: 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)

p n=all(\x->rem n x>0)[2..n-1]
a%0=rem a 4==3&&p(abs a)
0%a=a%0
a%b=p$a^2+b^2

Diese Lösung durchläuft nur alle Zahlen unter n, um zu prüfen, ob es sich um eine Primzahl handelt.

ungolfed version:

isprime = all (\x -> rem n x != 0) [2..n-1] -- none of the numbers between 2 and n-1 divide n.
isGaussianPrime a 0 = rem a 4==3 && isprime (abs a)
isGaussianPrime 0 a = isGaussianPrime a 0   -- the definition is symmetric
isGaussianPrime a b = isprime (a^2 + b^2)

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.)

s(p:x)=p:s[n|n<-x,rem n p>0] --the sieve function
l=s[2..]                     --infinite list of primes
p n=n==filter(>=n)l!!0       --check whether n is in the list of primes
a%0=rem a 4==3&&p(abs a)
0%a=a%0
a%b=p$a*a+b*b

ungolfed version:

primes = sieve [2..] where
    sieve (p:xs) = p:filter (\n -> rem n p /= 0) xs
isprime n = n == head (filter (>=n) primes) -- checks if the first prime >= n is equal to n. if it is, n is prime.
isGaussianPrime a 0 = rem a 4==3 && isprime (abs a)
isGaussianPrime 0 a = isGaussianPrime a 0   -- the definition is symmetric
isGaussianPrime a b = isprime (a^2 + b^2)

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.

stolzer haskeller
quelle
Nach meiner Zählung ist Ihre erste Lösung tatsächlich 77 Zeichen: D
killmous
Ich habe die Zeilenumbrüche gezählt, oder?
stolzer Haskeller
Ich zähle 74 reguläre Charaktere und 3 Zeilenumbrüche
mörderischer
du hast recht, es scheint, dass notepad ++ aus irgendeinem Grund Zeichen vor Zeilenumbrüchen hinzufügt. Vielen Dank!
stolzer Haskeller
deshalb benutze ich sublime;) helfe gerne weiter!
Killmous
9

C, 149 118 Zeichen

Bearbeitete Version (118 Zeichen):

int G(int a,int b){a=abs(a);b=abs(b);int n=a*b?a*a+b*b:a+b,
d=2;for(;n/d/d&&n%d;d++);return n/d/d|n<2?0:(a+b&3)>2|a*b;}

Dies ist eine einzelne Funktion:

  • G ( a , b ) gibt ungleich Null (wahr) zurück, wenn a + bi eine Gaußsche Primzahl ist, oder sonst Null (falsch).

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 auch a*bals Ersatz für a&&b(mit anderen Worten a!=0 && b!=0) und andere Tricks verwendet, bei denen der Operator Vorrang hat und die Ganzzahlteilung eine Rolle spielt. Zum Beispiel n/d/dist eine kürzere Art zu sagen n/d/d>=1, die eine überlaufsichere Art zu sagen ist n>=d*doder d*d<=noder im Wesentlichen d<=sqrt(n).


Originalfassung (149 Zeichen):

int Q(int n){int d=2;for(;n/d/d&&n%d;d++);return n/d/d||n<2;}
int G(int a,int b){a=abs(a);b=abs(b);return!((a|b%4<3|Q(b))*(b|a%4<3|Q(a))*Q(a*a+b*b));}

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:

Sample128

Todd Lehman
quelle
2
+1 für das Bild! Könnten Sie auch eine in etwa die gleiche Größe nur im ersten Quadranten (wegen der Symmetrie), es sieht wirklich gut aus hier =)
Fehler
Sie können einige Zeichen speichern, indem Sie d = 2; für (; n / d / d && n% d; d ++); mit für (d = 2; n / d / d & n% d ++;);
Alchymist
@Alchymist - Das spart zwar Zeichen, führt aber zu falschen Ergebnissen. Es ist wichtig, dass dies d++nicht als Teil der Bedingung geschieht, da es sonst die folgende Logik durcheinander bringt. Wenn Sie das d=2Innere der forSchleife verschieben, wird die Anzahl der Zeichen eher erhöht als verringert, da dies dimmer noch als intvor der forSchleife deklariert werden muss . Vermisse ich etwas?
Todd Lehman
Zu wahr. Die Gefahr, dies von einer Programmierumgebung wegzuschauen und nicht genau genug. Das Inkrementieren muss dort bleiben, wo es ist, und die Initialisierung hilft nur Ihrer ursprünglichen Lösung. Es gibt offensichtliche Einsparungen, wenn Sie n & d außerhalb der Funktion ohne Angabe von int deklarieren und in der for-Schleife initialisieren, aber ich gehe davon aus, dass Sie die Funktion in sich abgeschlossen haben, was eine strikte Interpretation der Anforderungen darstellt.
Alchymist
1
Die beste Testrunde ist hier spektakuläres Golfen! Sie können jedoch noch mehr Einsparungen erzielen, indem Sie die int-Typ-Bezeichner für den Rückgabetyp und die Argumente löschen und eine Variable für | a | verwenden + | b | und Optimierung der return-Anweisung: 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.
Feersum
4

APL (Dyalog Unicode) , 36 47 48 49 47 43 28 Bytes

Nimmt ein Array mit zwei Ganzzahlen a bund gibt den Booleschen Wert der Anweisung zurück a+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_falseanstelle von if_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.

{2=≢∪⍵∨⍳⍵}|+.×0∘∊⊃|{⍺⍵}3=4||

Probieren Sie es online!

Erläuterung

{2=≢∪⍵∨⍳⍵}|+.×0∘∊⊃|{⍺⍵}3=4||

                           |   abs(a), abs(b) or abs(list)
                       3=4|    Check if a and b are congruent to 3 (mod 4)
                  |{⍺⍵}        Combine with (abs(a), abs(b))
              0∘∊⊃             Pick out the original abs(list) if both are non-zero
                               Else pick out (if 3 mod 4)
          |+.×                 Dot product with abs(list) returns any of
                               - All zeroes if neither check passed
                               - The zero and the number that IS 3 mod 4
                               - a^2 + b^2
{2=≢∪⍵∨⍳⍵}                     Check if any of the above are prime, and return
Sherlock9
quelle
3

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.

a%1=[]
a%n|n`mod`a<1=a:2%(n`div`a)|1>0=(a+1)%n
0#b=2%d==[d]&&d`mod`4==3where d=abs(b)
a#0=0#a
a#b=2%c==[c]where c=a^2+b^2

Aufrufen als ghci ./gprimes.hsund dann können Sie es in der interaktiven Shell verwenden. Hinweis: Negative Zahlen sind heikel und müssen in Klammern gesetzt werden. Dh

*Main>1#1
True
*Main>(-3)#0
True
*Main>2#2
False
tödlich
quelle
3

Python - 121 120 Zeichen

def p(x,s=2):
 while s*s<=abs(x):yield x%s;s+=1
f=lambda a,b:(all(p(a*a+b*b))if b else f(b,a))if a else(b%4>2)&all(p(b))

pÜberprüft, ob abs(x)eine Primzahl vorliegt, indem alle Zahlen von 2 bis abs(x)**.5(was ist sqrt(abs(x))) durchlaufen werden . Es tut dies, indem es x % sfür jeden nachgibt s. allüberprüft dann, ob alle ausgegebenen Werte ungleich Null sind, und beendet die Generierung von Werten, sobald ein Divisor von angetroffen wird x. In f, f(b,a)ersetzt den Fall für b==0, inspiriert von @killmous 'Haskell Antwort.


-1 char und Bugfix von @PeterTaylor

hlt
quelle
Froh, dass ich helfen konnte :)
killmous
Sie könnten für eine Ersparnis von 2 s<abs(x)**.5mit ersetzen s*s<abs(x). Obwohl Sie wirklich prüfen sollten <=, so ist es wahrscheinlich zur Zeit fehlerhaft.
Peter Taylor
@ PeterTaylor Vielen Dank für den Hinweis auf den Fehler ...
hlt
Der Aufruf f(0,15)Ausbeute TypeError: unsupported operand type(s) for &: 'bool' and 'generator'mit meinem Dolmetscher. :(
Falko
f(0,15)gibt Falsefür mich sowohl auf 2.7.6 als auch auf 3.4.1 (unter OS X). Auf welcher Version bist du?
hlt
3

Python 2.7 , 341 301 253 Bytes, optimiert für Geschwindigkeit

lambda x,y:(x==0and g(y))or(y==0and g(x))or(x*y and p(x*x+y*y))
def p(n,r=[2]):a=lambda n:r+range(r[-1],int(n**.5)+1);r+=[i for i in a(n)if all(i%j for j in a(i))]if n>r[-1]**2else[];return all(n%i for i in r if i*i<n)
g=lambda x:abs(x)%4>2and p(abs(x))

Probieren Sie es online!

#pRimes. need at least one for r[-1]
r=[2]
#list of primes and other to-check-for-primarity numbers 
#(between max(r) and sqrt(n))
a=lambda n:r+list(range(r[-1],int(n**.5)+1))
#is_prime, using a(n)
f=lambda n:all(n%i for i in a(n))
#is_prime, using r
def p(n):
    global r
    #if r is not enough, update r
    if n>r[-1]**2:
        r+=[i for i in a(n) if f(i)]
    return all(n%i for i in r if i*i<n)
#sub-function for testing (0,y) and (x,0)
g=lambda x:abs(x)%4==3 and p(abs(x))
#the testing function
h=lambda x,y:(x==0 and g(y)) or (y==0 and g(x)) or (x and y and p(x*x+y*y))

Danke: 40 +48 - ganzes Golfen an Jo King

Alexey Burdin
quelle
Das fLambda ist auch nicht notwendig, zusammen mit dem listAnruf. 257 Bytes ohne diese, plus einige Leerzeichenentfernung. Das ist vielleicht nicht mehr so ​​effizient
Jo King,
(15,0) ist nun in der 257-Byte-Version wahr und die Laufzeit hat sich zu 5,5 Sekunden erhöht, sorry
Alexey Burdin
2

Perl - 110 107 105 Zeichen

Ich hoffe, ich habe die verknüpfte Definition korrekt befolgt ...

sub f{($a,$b)=map abs,@_;$n=$a**(1+!!$b)+$b**(1+!!$a);(grep{$n%$_<1}2..$n)<2&&($a||$b%4>2)&&($b||$a%4>2)}

Ungolfed:

sub f {
  ($a,$b) = map abs, @_;
  $n = $a**(1+!!$b) + $b**(1+!!$a);
  (grep {$n%$_<1} 2..$n)<2 && ($a || $b%4==3) && ($b || $a%4==3)
}

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 $aoder nicht. $bIch habe versucht, sie auf kürzestem Weg auszudrücken und sie einzugeben $n. Schließlich überprüfe ich, ob $nPrimzahl ist, indem ich zähle, wie viele Zahlen zwischen 2 und sich selbst ohne Rest teilen (das ist der grep...<2Teil), 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.

Tal
quelle
Ich kann es nicht für negative Parameter arbeiten.
Killmous
1
@killmous du hast recht, nur behoben
Tal
Können Sie den Algorithmus erklären?
stolzer Haskeller
1
Nett! Übrigens, ich denke, Sie könnten ein paar Charaktere abschneiden, indem Sie schreiben, $a%4>2anstatt $a%4==3.
Todd Lehman
2

Golflua 147 141

Die 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.

\p(x)s=2@s*s<=M.a(x)?(x%s==0)~0$s=s+1$~1$
\g(a,b)?a*b!=0~p(a^2+b^2)??a==0~p(b)+M.a(b)%4>2??b==0~p(a)+M.a(a)%4>2!?~0$$
w(g(tn(I.r()),tn(I.r())))

Gibt 1 zurück, wenn wahr, und 0, wenn nicht.

Eine ungolfed Lua Version,

-- prime number checker
function p(x)
   s=2
   while s*s<=math.abs(x) do
      if(x%s==0) then return 0 end
      s=s+1
   end
   return 1
end

-- check gaussian primes
function g(a,b)
   if a*b~=0 then
      return p(a^2+b^2)
   elseif a==0 then
      return p(b) + math.abs(b)%4>2
   elseif b==0 then
      return p(a) + math.abs(a)%4>2
   else
      return 0
   end
end


a=tonumber(io.read())
b=tonumber(io.read())
print(g(a,b))
Kyle Kanos
quelle
Sie können 6 Zeichen einsparen, indem Sie am Ende einfach tonumber(io.read())als Argument geinfügen, und 2 weitere, indem Sie die Zeilenumbrüche entfernen
mniip
@mniip: Die Zeilenumbrüche wurden nicht gezählt, ich habe sie nur der Übersichtlichkeit halber hinzugefügt (kein seitliches Scrollen). Ich werde das Einlesen von g aktualisieren, wenn ich in Kürze zur Arbeit komme. Vielen Dank!
Kyle Kanos
Funktioniert es bei großen Stückzahlen immer noch in angemessener Zeit? Ich dachte , in erster Linie über die Art und Weise bruteforcing alle Gaußschen ganzen Zahlen zu prüfen , awo , |a| <= |z|wenn a | z(falls adividieren z).
Fehler
@flawr: Ich habe es mit a = 2147483644, b = 896234511 getestet und in ca. 0,002 s 0 erhalten. Ich habe es auch mit 2147483629 und 2147483587 (zwei sehr große Primzahlen) getestet und in weiteren 0,002 s 0 erhalten. Ich versuche ein großes Zahlenpaar so zu finden, dass a ^ 2 + b ^ 2 Primzahl ist und stelle sicher, dass ich eine funktionierende Lösung für so große Zahlen habe.
Kyle Kanos
@flawr: Getestet mit a = 4600 & b = 5603 (a ^ 2 + b ^ 2 = 2147393609 ist prim & <2 ^ 32-1) und es dauerte die gleichen 0,002 Sekunden, um 1 zurückzugeben. Yay!
Kyle Kanos
1

APL (NARS), 99 Zeichen, 198 Byte

r←p w;i;k
r←0⋄→0×⍳w<2⋄i←2⋄k←√w⋄→3
→0×⍳0=i∣w⋄i+←1
→2×⍳i≤k
r←1

f←{v←√k←+/2*⍨⍺⍵⋄0=⍺×⍵:(p v)∧3=4∣v⋄p k}

Prüfung:

  0 f 13
0
  0 f 9
0
  2 f 3
1
  3 f 4
0
  0 f 7
1
  0 f 9
0
  4600 f 5603
1  
RosLuP
quelle
1

Runenverzauberungen , 41 Bytes

>ii:0)?\S:0)?\:*S:*+'PA@
3%4A|'S/;$=?4/?3

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:

>ii:0)?\S:0)?\:*S:*+'PA@
3%4A|'S/!   S/;$=

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).

Draco18s
quelle
1

Mathematica, 149 Zeichen

If[a==0,#[[3]]&&Mod[Abs@b,4]==3,If[b==0,#[[2]]&&Mod[Abs@a,4]==3,#[[1]]]]&[(q=#;Total[Boole@IntegerQ[q/#]&/@Range@q]<3&&q!=0)&/@{a^2+b^2,Abs@a,Abs@b}]

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:

MyIsPrime[p_] := (q = Abs@p; 
  Total[Boole@IntegerQ[q/#] & /@ Range@q] < 3 && q != 0)

Bonusplot aller Gaußschen Primzahlen von -20 bis 20:

Handlung von Gaußschen Primzahlen

ralian
quelle
1

Ruby -rprime , 65 60 80 Bytes

Die Regel "isPrime kann nicht verwendet werden" wurde nicht beachtet ...

->a,b{r=->n{(2...n).all?{|i|n%i>0}};c=(a+b).abs;r[a*a+b*b]||a*b==0&&r[c]&&c%4>2}

Probieren Sie es online!

Wert Tinte
quelle
0

Python - 117 122 121

def f(a,b):
 v=(a**2+b**2,a+b)[a*b==0]
 for i in range(2,abs(v)):
  if v%i<1:a=b=0
 return abs((a,b)[a==0])%4==3or a*b!=0
Falko
quelle
Da 3 die größte Zahl ist, die eine Mod 4 sein kann, könnten Sie die ==3mit>2
FlipTack