23
3
A Gaussian integer is a complex number whose real and imaginary parts are integers.
Gaussian integers, like ordinary integers, can be represented as a product of Gaussian primes, in a unique manner. The challenge here is to calculate the prime constituents of a given Gaussian integer.
Input: a Gaussian integer, which is not equal to 0 and is not a unit (i.e. 1, -1, i and -i can not be given as inputs). Use any sensible format, for example:
- 4-5i
- -5*j+4
- (4,-5)
Output: a list of Gaussian integers, which are prime (i.e. no one of them can be represented as a product of two non-unit Gaussian integers), and whose product is equal to the input number. All numbers in the output list must be non-trivial, i.e. not 1, -1, i or -i. Any sensible output format can be used; it should not necessarily be the same as input format.
If the output list has more than 1 element, then several correct outputs are possible. For example, for input 9 the output can be [3, 3] or [-3, -3] or [3i, -3i] or [-3i, 3i].
Test cases, (taken from this table; 2 lines per test case)
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
Built-in functions for factoring Gaussian integers are not allowed. Factoring ordinary integers by built-in functions is allowed though.
Should
3i
return as3,i
, or3i
? – Value Ink – 2017-07-12T22:05:03.9633i
is the correct answer becausei
is not a prime. I have updated the test case to make it clearer. – anatolyg – 2017-07-12T22:14:30.010is -3-2j, 2-1j, -1-1j a correct answer for factorization of 7+9j ? – mdahmoune – 2017-07-12T23:04:18.563
@mdahmoune they multiply to the correct number, so I don't see why not. The spec mentions several correct outputs are possible. – Value Ink – 2017-07-12T23:06:18.947
4
According to Wolfram Alpha,
– Value Ink – 2017-07-12T23:34:23.8506840+585i
has the wrong list of factors, as5
is not a Gaussian prime. Instead, it returns-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i
. Source1FYI,
256=(1+i)**16
not(1+i)**8
because256=2**8=(2i)**8
and2i=(1+i)**2
– Shieru Asakoto – 2018-02-23T05:59:39.937