Liczba całkowita Gaussa jest liczbą zespoloną, której rzeczywistą i urojoną częścią są liczby całkowite.

Liczby całkowite Gaussa, podobnie jak zwykłe liczby całkowite, można przedstawić w unikalny sposób jako iloczyn liczb pierwszych Gaussa. Wyzwaniem jest tutaj obliczenie głównych składników danej liczby całkowitej Gaussa.

Dane wejściowe: liczba całkowita Gaussa, która nie jest równa 0 i nie jest jednostką (tzn. 1, -1, i oraz -i nie mogą być podawane jako dane wejściowe). Użyj dowolnego rozsądnego formatu, na przykład:

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

Dane wyjściowe: lista liczb całkowitych Gaussa, które są liczbą pierwszą (tzn. Żadnej z nich nie można przedstawić jako iloczynu dwóch niejednostkowych liczb całkowitych Gaussa), i których iloczyn jest równy liczbie wejściowej. Wszystkie liczby na liście wyjściowej muszą być nietrywialne, tzn. Nie 1, -1, i lub -i. Można zastosować dowolny rozsądny format wyjściowy; niekoniecznie powinien być taki sam jak format wejściowy.

Jeśli lista wyjściowa zawiera więcej niż 1 element, wówczas możliwych jest kilka poprawnych wyników. Na przykład dla wejścia 9 wyjściem może być [3, 3] lub [-3, -3] lub [3i, -3i] lub [-3i, 3i].

Przypadki testowe (wzięte z tej tabeli ; 2 wiersze na przypadek testowy)

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

Wbudowane funkcje faktorowania liczb całkowitych Gaussa są niedozwolone. Dozwolone jest jednak uwzględnianie zwykłych liczb całkowitych według wbudowanych funkcji.

Galaretka , 61 55 bajtów

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

Wypróbuj online! (Nagłówek i stopka formatują dane wyjściowe)

-6 bajtów dzięki @EricTheOutgolfer

Jak to działa

Ḟ,Ċ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

Rubinowy , 258 256 249 246 + 8 = 264 257 254 bajtów

Używa -rprimeflagi.

Rany, co za bałagan.

Używa tego algorytmu z przepływu stosu.

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

Wypróbuj online!

Python 2 , 250 239 223 215 bajtów

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

Wypróbuj online!

• -11 bajtów podczas używania argumentów funkcji wielu
• -2² * ² bajtów przy użyciu jednej zmiennej do analizowania par (a,b)
• -2³ bajtów podczas mieszania tabulatorów i spacji: dzięki ovs

Niektóre wyjaśnienia rekurencyjnie rozkładają kompleks na dwa kompleksy, dopóki rozkład nie jest możliwy ...

Rdza - 212 bajtów

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

Nie jestem w 100% pewien, czy to działa w 100% poprawnie, ale wydaje się, że jest poprawne w przypadku szerokiego zakresu testów. To nie jest mniejsze niż Jelly, ale przynajmniej jest mniejsze niż języki interpretowane (jak dotąd). Wydaje się również, że jest szybszy i może pracować z wejściami o wartości miliarda wielkości w mniej niż sekundę. Na przykład współczynniki 1234567890 + 3141592650i jako (-9487 + 7990i) (- 1 + -1i) (- 395 + 336i) (2 + -1i) (1 + 1i) (3 + 0i) (3 + 0i) (4+ 1i) (- 1 + 1i) (- 1 + 2i), (kliknij tutaj, aby przetestować na wolfram alfa)

Zaczęło się od tego samego pomysłu, co naiwne faktoring liczb całkowitych, aby przejść przez każdą liczbę poniżej danej liczby całkowitej, sprawdzić, czy dzieli, powtarzaj, aż zrobisz. Następnie, zainspirowany innymi odpowiedziami, przekształcił się ... wielokrotnie uwzględnia elementy w wektorze. Robi to wiele razy, ale nie do niczego. Liczba iteracji została wybrana, aby objąć sporą część rozsądnych danych wejściowych.

Nadal używa „(mod b) == 0”, aby sprawdzić, czy jedna liczba całkowita dzieli drugą (dla Gaussów używamy wbudowanego modulusa gaussowskiego Rust i uważamy „0” za normę == 0), jednak sprawdzenie „norm” a / b)! = 1 'zapobiega dzieleniu „za dużo”, w zasadzie pozwalając, aby powstały wektor był wypełniony tylko liczbami pierwszymi, ale nie sprowadzając żadnego elementu wektora do jedności (0-i, 0 + i, -1 + 0i, 1 + 0i) (co jest zabronione przez pytanie).

Limity dla pętli for ustalono eksperymentalnie. y zmienia się od 1 do góry, aby zapobiec panice dzielenia przez zero, a x może przejść od -999 do 0 dzięki lustrzanemu odwróceniu Gaussów nad kwadrantami (myślę?). Jeśli chodzi o ograniczenia, pierwotne pytanie nie wskazywało prawidłowego zakresu danych wejściowych / wyjściowych, więc zakłada się „rozsądny rozmiar wejściowy” ... (Edytuj ... jednak nie jestem pewien, jak obliczyć, przy której liczbie to będzie zaczynają „zawodzić”, wyobrażam sobie, że istnieją liczby całkowite Gaussa, których nie da się podzielić przez nic poniżej 999, ale nadal są dla mnie zaskakująco małe)

Wypróbuj nieco nie golfową wersję na play.rust-lang.org

Perl 6 , 141 124 bajtów

Dzięki Jo King za -17 bajtów

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

Wypróbuj online!

Pyth , 54 51 45 42 36 bajtów

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

Wypróbuj online!

Można wprowadzać w postaci 1+2j- Liczby rzeczywiste i urojone czysto można pominąć drugi składnik (na przykład 9, 2j). Dane wyjściowe to oddzielona nowym wierszem lista liczb zespolonych w formie (1+2j), w której liczby czysto urojone pomijają część rzeczywistą.

Wykorzystuje to prosty podział szlaku, generując wszystkie liczby całkowite gaussowskie o wielkości większej niż 1 i mniejszej niż bieżąca wartość plus sama wartość. Są one filtrowane, aby zachować te, które są współczynnikiem wartości, a najmniejszy pod względem wielkości jest wybierany jako następny czynnik pierwszy. To jest wynik, a wartość jest przez niego dzielona, ​​aby uzyskać wartość dla następnej iteracji.

Poza tym Pyth pokonuje Jelly 😲 (nie sądzę jednak, żeby to trwało)

 .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