Faktorisieren Sie eine Gaußsche Ganzzahl

23

Eine Gaußsche Ganzzahl ist eine komplexe Zahl, deren Real- und Imaginärteil ganze Zahlen sind.

Gaußsche Ganzzahlen können wie gewöhnliche Ganzzahlen auf einzigartige Weise als Produkt von Gaußschen Primzahlen dargestellt werden. Hier besteht die Herausforderung darin, die Hauptbestandteile einer bestimmten Gaußschen Ganzzahl zu berechnen.

Eingabe: Eine Gaußsche Ganzzahl, die ungleich 0 ist und keine Einheit darstellt (dh 1, -1, i und -i können nicht als Eingabe angegeben werden). Verwenden Sie ein sinnvolles Format, zum Beispiel:

  • 4-5i
  • -5 * j + 4
  • (4, -5)

Ausgabe: Eine Liste von Gaußschen Ganzzahlen, die Primzahlen sind (dh keine von ihnen kann als Produkt von zwei nichteinheitlichen Gaußschen Ganzzahlen dargestellt werden) und deren Produkt gleich der eingegebenen Zahl ist. Alle Zahlen in der Ausgabeliste dürfen nicht trivial sein, dh nicht 1, -1, i oder -i. Jedes sinnvolle Ausgabeformat kann verwendet werden. Es muss nicht unbedingt dasselbe sein wie das Eingabeformat.

Wenn die Ausgabeliste mehr als ein Element enthält, sind mehrere korrekte Ausgaben möglich. Für Eingang 9 kann der Ausgang beispielsweise [3, 3] oder [-3, -3] oder [3i, -3i] oder [-3i, 3i] sein.

Testfälle (aus dieser Tabelle entnommen ; 2 Zeilen pro Testfall)

2
1+i, 1-i

3i
3i

256
1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i

7+9i
1+i,2−i,3+2i

27+15i
1+i,3,7−2i

6840+585i
-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i

Integrierte Funktionen zum Faktorisieren von Gaußschen Ganzzahlen sind nicht zulässig. Das Berücksichtigen gewöhnlicher Ganzzahlen durch integrierte Funktionen ist jedoch zulässig.

anatolyg
quelle
Sollte 3ials zurückkehren 3,i, oder 3i?
Value Ink
3iist die richtige Antwort, weil ies keine Primzahl ist. Ich habe den Testfall aktualisiert, um ihn klarer zu machen.
Anatolyg
ist -3-2j, 2-1j, -1-1j eine richtige Antwort für die Faktorisierung von 7 + 9j?
mdahmoune
4
Laut Wolfram Alpha 6840+585iist die Liste der Faktoren falsch, da 5es sich nicht um eine Gaußsche Primzahl handelt. Stattdessen kehrt es zurück -1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i. Quelle
Wert Tinte
1
Zu 256=(1+i)**16(1+i)**8256=2**8=(2i)**82i=(1+i)**2
Ihrer Information

Antworten:

4

Jelly , 61-55 Bytes

Ḟ,Ċ1ḍP
Ḟ,ĊḤp/-,1p`¤×€×1,ıFs2S€⁸÷ÇÐfỊÐḟ1;Ṫð,÷@\ḟ1
Ç€F$ÐL

Probieren Sie es online! (Kopf- und Fußzeile formatieren die Ausgabe)

-6 Bytes dank @EricTheOutgolfer

Wie es funktioniert

Ḟ,Ċ1ḍP  - helper function: determines if a complex number is Gaussian
Ḟ,Ċ       - real, complex components
   1ḍ     - set each to if 1 divides them
     P    - all

Ḟ,ĊḤp/-,1p`¤×€×1,ıFs2S€⁸÷ÇÐfỊÐḟ1;Ṫð,÷@\ḟ1 - helper: outputs a factor pair of the input
Ḟ,ĊḤp/                   - creates a list of possible factors a+bi, a,b>=0
      -,1p`¤×€           - extend to the other three quadrants 
              ×1,ıFs2S€  - convert to  actual complex numbers 
⁸÷                       - get quotient with input complex number
  ÇÐf                    - keep only Gaussian numbers (using helper function)
     ỊÐḟ                 - remove units (i,-i,1,-1)
        1;               - append a 1 to deal with primes having no non-unit factors
          Ṫð,÷@\         - convert to a factor pair
                ḟ1       - remove 1s
Ç€F$ÐL
Ç€      - factor each number
   $    - and
  F     - flatten the list
    ÐL  - until factoring each number and flattening does not change the list
fireflame241
quelle
Wenn hier "Behalte nur Gauß" steht, heißt das dann "Behalte nur Primzahlen"?
Don Bright
@donbright nein, es bezieht sich nur auf die komplexen Zahlen mit ganzzahligen reellen und komplexen Komponenten
fireflame241
@ fireflame241 oh ich sehe jetzt! Vielen Dank
Don Bright
5

Ruby , 258 256 249 246 + 8 = 264 257 254 Bytes

Verwendet die -rprimeFlagge.

Meine Güte, was für ein Durcheinander.

Verwendet diesen Algorithmus von Stackoverflow.

->c{m=->x,y{x-y*eval("%d+%di"%(x/y).rect)};a=c.abs2.prime_division.flat_map{|b,e|b%4<2?(1..e).map{k=(2..d=b).find{|n|n**(~-b/2)%b==b-1}**(~-b/4)%b+1i;d,k=k,m[d,k]while k!=0;c/=d=m[c,d]==0?d:d.conj;d}:(c/=b<3?(b=1+1i)**e:b**e/=2;[b]*e)};a[0]*=c;a}

Probieren Sie es online!

Wert Tinte
quelle
5

Python 2 , 250 239 223 215 Bytes

e,i,w=complex,int,abs
def f(*Z):
 if Z:
	z=Z[0];q=i(w(z));Q=4*q*q
	while Q>0:
 	 a=Q/q-q;b=Q%q-q;x=e(a,b)
 	 if w(x)>1:
		y=z/x
		if w(y)>1 and y==e(i(y.real),i(y.imag)):f(x,y);z=Q=0
 	 Q-=1
	if z:print z
	f(*Z[1:])

Probieren Sie es online!

  • -11 Byte bei Verwendung mehrerer Funktionsargumente
  • -2² * ² Bytes bei Verwendung einer Variablen zum Parsen von Paaren (a,b)
  • -2³ Bytes beim Mischen von Tabulatoren und Leerzeichen: dank ovs

Einige Erklärungen zerlegen einen Komplex rekursiv in zwei Komplexe, bis keine Zerlegung mehr möglich ist ...

mdahmoune
quelle
Nun, bei größeren Eingängen tritt in TIO ein Timeout auf, aber es ist kürzer als meine Ruby-Antwort ... fürs Erste . Außerdem def f(Z,s=[])sollten Sie einen Charakter speichern
Value Ink
@ValueInk Ja, es ist langsamer als Ihre Rubin-Lösung
mdahmoune
2
Interessantes Muster mit der Einrückung ...
Erik der Outgolfer
@ ValueInk Multiple Function Arguments speichert mehr Bytes :)
mdahmoune
1
Sie können Ihre Byteanzahl durch reduzieren Tabs und Leerzeichen Misch
ovs
3

Rust - 212 Bytes

use num::complex::Complex as C;fn f(a:&mut Vec<C<i64>>){for _ in 0..2{for x in -999..0{for y in 1..999{for i in 0..a.len(){let b=C::new(x,y);if(a[i]%b).norm_sqr()==0&&(a[i]/b).norm_sqr()>1{a[i]/=b;a.push(b)}}}}}}

Ich bin nicht zu 100% sicher, ob dies zu 100% korrekt funktioniert, aber es scheint für eine Vielzahl von Tests richtig zu sein. Dies ist nicht kleiner als Jelly, aber zumindest ist es kleiner als die (bisher) interpretierten Sprachen. Es scheint auch schneller zu sein und kann Eingaben mit einer Größenordnung von einer Milliarde in weniger als einer Sekunde verarbeiten. Zum Beispiel faktoriert 1234567890 + 3141592650i als (-9487 + 7990i) (-1 + -1i) (-395 + 336i) (2 + -1i) (1 + 1i) (3 + 0i) (3 + 0i) (4+ 1i) (- 1 + 1i) (- 1 + 2i), (hier klicken, um auf Wolfram Alpha zu testen)

Dies begann mit der gleichen Idee wie das naive Faktorisieren von ganzen Zahlen, um jede Zahl unter der fraglichen ganzen Zahl durchzugehen, zu sehen, ob sie sich teilt, und zu wiederholen, bis es fertig ist. Dann, inspiriert von anderen Antworten, wandelte es sich ... es faktorisiert wiederholt Elemente in einem Vektor. Es tut dies eine gute Anzahl von Malen, aber nicht "bis" irgendetwas. Die Anzahl der Iterationen wurde gewählt, um einen guten Teil der sinnvollen Eingaben abzudecken.

Es wird immer noch "(a mod b) == 0" verwendet, um zu testen, ob eine Ganzzahl eine andere teilt (für Gaußsche verwenden wir eingebautes Rust-Gaußsches Modulo und betrachten "0" als Norm == 0), jedoch die Prüfung auf "norm" ( a / b)! = 1 'verhindert, dass "zu viel" geteilt wird, so dass der resultierende Vektor im Grunde genommen nur mit Primzahlen gefüllt werden kann, aber kein Element des Vektors auf Einheit reduziert wird (0-i, 0 + i, -1 +) 0i, 1 + 0i) (was durch die Frage verboten ist).

Die for-loop-Grenzen wurden experimentell ermittelt. y geht von 1 auf, um eine Panik beim Teilen durch Null zu vermeiden, und x kann dank der Spiegelung der Gaußschen über die Quadranten von -999 auf 0 gehen (glaube ich?). In Bezug auf die Einschränkungen gab die ursprüngliche Frage keinen gültigen Bereich für die Eingabe / Ausgabe an, daher wird eine "angemessene Eingabegröße" angenommen ... (Bearbeiten ... ich bin jedoch nicht genau sicher, wie mit welcher Zahl dies berechnet werden soll Ich stelle mir vor, dass es Gaußsche Ganzzahlen gibt, die durch nichts unter 999 teilbar sind, aber für mich immer noch überraschend klein sind.

Probieren Sie die etwas ungolfed Version auf play.rust-lang.org

Don Bright
quelle
3

Perl 6 , 141 124 Bytes

Vielen Dank an Jo King für -17 Bytes

sub f($_){{$!=0+|sqrt .abs²-$^a²;{($!=$_/my \w=$^b+$a*i)==$!.floor&&.abs>w.abs>1>return f w&$!}for -$!..$!}for ^.abs;.say}

Probieren Sie es online!

bb94
quelle
wie funktioniert das? ist der boden ein maßgefertigter modulo?
Don Bright
1
@donbright Der floorTeil prüft, ob $_/w(dh der aktuelle Faktor durch eine Zahl geteilt) eine ganze Zahl ist
Jo King
2

Pyth , 54 51 45 42 36 Bytes

 .W>H1cZ
h+.aDf!%cZT1>#1.jM^s_BM.aZ2

Probieren Sie es online!

Akzeptiert Eingaben in Form 1+2j- rein reelle oder imaginäre Zahlen die andere Komponente auslassen können (z 9, 2j). Die Ausgabe ist eine durch Zeilenumbrüche getrennte Liste komplexer Zahlen in der Form (1+2j), wobei rein imaginäre Zahlen den Realteil weglassen.

Hierbei wird eine einfache Aufteilung der Pfade verwendet, bei der alle Gaußschen Ganzzahlen mit einer Größe größer als 1 und kleiner als der aktuelle Wert plus dem Wert selbst generiert werden. Diese werden gefiltert, um diejenigen Werte beizubehalten, die ein Faktor des Werts sind, und der kleinste Wert wird als nächster Primfaktor ausgewählt. Dies wird ausgegeben und der Wert wird durch ihn geteilt, um den Wert für die nächste Iteration zu erhalten.

Außerdem schlägt Pyth Jelly 😲 (ich erwarte aber nicht, dass es hält)

 .W>H1cZ¶h+.aDf!%cZT1>#1.jM^s_BM.aZ2ZQ   Implicit: Q=eval(input())
                                         Newline replaced with ¶, trailing ZQ inferred
 .W                                  Q   While <condition>, execute <inner>, with starting value Q
   >H1                                   Condition function, input H
   >H1                                     Is magnitude of H > 1?
                                           This ensures loop continues until H is a unit, i.e. 1, -1, j, or -j)
      cZ¶h+.aDf!%cZT1>#1.jM^s_BM.aZ2Z    Inner function, input Z
                                .aZ        Take magnitude of Z

                             _BM           Pair each number in 0-indexed range with its negation
                            s              Flatten
                           ^       2       Cartesian product of the above with itself
                        .jM                Convert each pair to a complex number
                      #                    Filter the above to keep those element where...
                     > 1                   ... the magnitude is greater than 1 (removes units)
              f                            Filter the above, as T, to keep where:
                 cZT                         Divide Z by T
                %   1                        Mod real and imaginary parts by 1 separately
                                             If result of division is a gaussian integer, the mod will give (0+0j)
               !                             Logical NOT - maps (0+0j) to true, all else to false
                                           Result of filter are those gaussian integers which evenly divide Z
           .aD                             Sort the above by their magnitudes
          +                         Z      Append Z - if Z is ±1±1j, the filtered list will be empty
         h                                 Take first element, i.e. smallest factor
        ¶                                  Print with a newline
      cZ                                   Divide Z by that factor - this is new input for next iteration
                                         Output of the while loop is always 1 (or -1, j, or -j) - leading space suppesses output
Sok
quelle
Das ist sehr interessant, aber es scheint eine Zeitüberschreitung auf 6840 + 585j
don bright
@donbright Tut es auf TIO, da es ein Verarbeitungslimit von 60s hat. Es funktioniert mit mehr Zeit, wenn Sie es also lokal ausführen, sollte es ohne Probleme funktionieren.
Sok