Gaussian целое представляет собой комплексное число, действительные и мнимые части являются целыми числами.

Гауссовы целые числа, как и обычные целые, могут быть представлены как произведение гауссовых простых чисел уникальным образом. Задача здесь состоит в том, чтобы вычислить простые составляющие данного гауссова целого числа.

Входные данные: гауссово целое число, которое не равно 0 и не является единицей (т. Е. 1, -1, i и -i не могут быть заданы в качестве входных данных). Используйте любой разумный формат, например:

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

Вывод: список гауссовых целых чисел, которые являются простыми (т.е. ни одно из них не может быть представлено как произведение двух неединичных гауссовых целых чисел), и произведение которых равно входному числу. Все числа в списке вывода должны быть нетривиальными, т. Е. Не 1, -1, i или -i. Любой разумный выходной формат может быть использован; он не обязательно должен совпадать с форматом ввода.

Если список вывода содержит более 1 элемента, возможны несколько правильных выходов. Например, для входа 9 выход может быть [3, 3] или [-3, -3] или [3i, -3i] или [-3i, 3i].

Контрольные примеры (из этой таблицы ; 2 строки на контрольный пример)

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

Встроенные функции для факторизации гауссовых целых чисел не допускаются. Факторинг обычных целых чисел встроенными функциями допускается.

Желе , 61 55 байт

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

Попробуйте онлайн! (Верхний и нижний колонтитулы форматируют вывод)

-6 байт благодаря @EricTheOutgolfer

Как это работает

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

Рубин , 258 256 249 246 + 8 = 264 257 254 байта

Использует -rprimeфлаг.

Боже, какой беспорядок.

Использует этот алгоритм из 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}

Попробуйте онлайн!

Python 2 , 250 239 223 215 байт

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

Попробуйте онлайн!

• -11 байт при использовании аргументов с несколькими функциями
• -2² * ² байт при использовании одной переменной для разбора пар (a,b)
• -2³ байта при смешивании табуляции и пробелов: благодаря ovs

Некоторое объяснение рекурсивно разлагает комплекс на два комплекса, пока разложение невозможно ...

Ржавчина - 212 байт

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

Я не уверен на 100%, работает ли это на 100% правильно, но кажется, что это правильно для большого диапазона тестов. Это не меньше, чем желе, но, по крайней мере, он меньше, чем интерпретируемые языки (пока). Он также кажется более быстрым и может работать за счет миллиардов величин менее чем за секунду. Например, 1234567890 + 3141592650i коэффициенты как (-9487 + 7990i) (- 1 + -1i) (- 395 + 336i) (2 + -1i) (1 + 1i) (3 + 0i) (3 + 0i) (4+ 1i) (- 1 + 1i) (- 1 + 2г), (нажмите здесь, чтобы проверить альфа вольфрама)

Это началось с той же идеи, что и наивный факторинг целых чисел, чтобы просмотреть каждое число ниже целого числа, посмотреть, делит ли оно, повторить до конца. Затем, вдохновленный другими ответами, он трансформировался ... он многократно учитывает элементы в векторе. Он делает это много раз, но не до тех пор, пока «ничего». Количество итераций было выбрано, чтобы охватить большую часть разумных входных данных.

Он по-прежнему использует "(a mod b) == 0", чтобы проверить, делит ли одно целое число на другое (для гауссиан мы используем встроенный модуль Rust по Гауссу по модулю и считаем "0" нормой == 0), однако проверка для 'нормы ( a / b)! = 1 'предотвращает деление «слишком много», в основном позволяя заполнить результирующий вектор только простыми числами, но не переводя ни один элемент вектора в единицу (0-i, 0 + i, -1 + 0i, 1 + 0i) (что запрещено вопросом).

Пределы для петли были найдены в ходе эксперимента. y переходит от 1 кверху, чтобы предотвратить панику деления на ноль, а x может переходить от -999 до 0 благодаря отражению гауссиан над квадрантами (я думаю?). Что касается ограничений, то в первоначальном вопросе не был указан допустимый диапазон ввода / вывода, поэтому предполагается «разумный размер ввода» ... (Правка ... однако я не совсем уверен, как рассчитать, по какому числу это будет начинаю "терпеть неудачу", я думаю, что есть гауссовы целые числа, которые не делятся ничем ниже 999, но все еще удивительно малы для меня)

Попробуй версию без пристрастия на play.rust-lang.org

Perl 6 , 141 124 байта

Спасибо Джо Кингу за -17 байт

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

Попробуйте онлайн!

Pyth , 54 51 45 42 36 байт

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

Попробуйте онлайн!

Принимает ввод в виде 1+2j- чисто действительные или мнимые числа могут опускать другие компоненты (например 9, 2j). Выходные данные - это разделенный новой строкой список комплексных чисел в форме(1+2j) с чисто мнимыми числами, пропускающими действительную часть.

При этом используется простое деление трейла, генерирующее все гауссовы целые числа с величиной больше 1 и меньше текущего значения, а также самого значения. Они фильтруются, чтобы сохранить те, которые являются фактором значения, и наименьшее по величине выбирается в качестве следующего основного фактора. Это вывод, и значение делится на него, чтобы получить значение для следующей итерации.

Кроме того, Пиф избивает Желе though (хотя я не ожидаю, что это продлится)

 .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