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.

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

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!

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

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

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!

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