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.
źródło
3i
wrócić jak3,i
, lub3i
?3i
jest poprawną odpowiedzią, ponieważi
nie jest liczbą pierwszą. Zaktualizowałem przypadek testowy, aby był bardziej przejrzysty.6840+585i
ma niewłaściwą listę czynników, ponieważ5
nie jest liczbą gaussowską. Zamiast tego zwraca-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i
. Źródło256=(1+i)**16
nie(1+i)**8
dlatego256=2**8=(2i)**8
i2i=(1+i)**2
Odpowiedzi:
Galaretka ,
6155 bajtówWypróbuj online! (Nagłówek i stopka formatują dane wyjściowe)
-6 bajtów dzięki @EricTheOutgolfer
Jak to działa
źródło
Rubinowy ,
258256249246 + 8 =264257254 bajtówUżywa
-rprime
flagi.Rany, co za bałagan.
Używa tego algorytmu z przepływu stosu.
Wypróbuj online!
źródło
Python 2 ,
250239223215 bajtówWypróbuj online!
(a,b)
Niektóre wyjaśnienia rekurencyjnie rozkładają kompleks na dwa kompleksy, dopóki rozkład nie jest możliwy ...
źródło
def f(Z,s=[])
powinien ocalić ci postaćRdza - 212 bajtów
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
źródło
Perl 6 ,
141124 bajtówDzięki Jo King za -17 bajtów
Wypróbuj online!
źródło
floor
Część sprawdza, czy$_/w
(tj. bieżący współczynnik podzielony przez liczbę) jest liczbą całkowitąPyth ,
5451454236 bajtówWypróbuj online!
Można wprowadzać w postaci
1+2j
- Liczby rzeczywiste i urojone czysto można pominąć drugi składnik (na przykład9
,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)
źródło