Faktoryzuj liczbę całkowitą Gaussa

23

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.

anatolig
źródło
Powinien 3iwrócić jak 3,i, lub 3i?
Wartość tuszu
3ijest poprawną odpowiedzią, ponieważ inie jest liczbą pierwszą. Zaktualizowałem przypadek testowy, aby był bardziej przejrzysty.
anatolyg
czy -3-2j, 2-1j, -1-1j jest poprawną odpowiedzią na faktoryzację 7 + 9j?
mdahmoune,
4
Według Wolfram Alpha 6840+585ima niewłaściwą listę czynników, ponieważ 5nie jest liczbą gaussowską. Zamiast tego zwraca -1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i. Źródło
Value Ink
1
Do twojej wiadomości, 256=(1+i)**16nie (1+i)**8dlatego 256=2**8=(2i)**8i2i=(1+i)**2
Shieru Asakoto

Odpowiedzi:

4

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
fireflame241
źródło
kiedy to mówi „zachowaj tylko Gaussa”, czy to oznacza „zachowaj tylko liczby pierwsze”?
don jasny
@donbright nie, odnosi się to do zachowania tylko tych liczb zespolonych za pomocą liczb całkowitych rzeczywistych i złożonych
fireflame241
@ fireflame241 oh widzę teraz! dziękuję bardzo
don jasne
5

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!

Wartość tuszu
źródło
5

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

mdahmoune
źródło
Cóż, przekracza limit czasu w TIO przy większych wejściach, ale jest krótszy niż moja odpowiedź Ruby ... na razie . Ponadto def f(Z,s=[])powinien ocalić ci postać
Value Ink
@ValueInk tak, jest wolniejszy niż twoje rozwiązanie ruby
mdahmoune
2
Ciekawy wzór z wcięciem ...
Erik Outgolfer
@ValueInk Wiele argumentów funkcji oszczędza więcej bajtów :)
mdahmoune
1
Możesz zmniejszyć liczbę bajtów, mieszając tabulatory i spacje
2017
3

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

Don Bright
źródło
3

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!

bb94
źródło
jak to działa? czy podłoga jest niestandardowym modułem?
don jasny
1
@donbright floorCzęść sprawdza, czy $_/w(tj. bieżący współczynnik podzielony przez liczbę) jest liczbą całkowitą
Jo King
2

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
Sok
źródło
jest to bardzo interesujące, ale wydaje się, że upłynął limit 6840 + 585j
don Bright
@donbright Robi to w TIO, ponieważ ma limit przetwarzania 60s. Będzie działał dłużej, więc jeśli uruchamiasz go lokalnie, powinien działać bez problemu.
Sok