Project Nayuki


Factorize Gaussian integer (JavaScript)

Program

Factorization:  

Description

This JavaScript program calculates the prime factorization of the given Gaussian integer. A Gaussian integer is a complex number of the form a + bi, where a and b are integers. This program has a limit of |a|, |b| < 226. If the number is large, the program may hang for a few seconds.

The factorization is put into the following canonical form:

The source code is available for viewing.

Examples

Input format

List of Gaussian primes

List of all Gaussian primes up to norm 1000 (with symmetries removed): (1 + 1i), (2 + 1i), (3 + 0i), (3 + 2i), (4 + 1i), (5 + 2i), (6 + 1i), (5 + 4i), (7 + 0i), (7 + 2i), (6 + 5i), (8 + 3i), (8 + 5i), (9 + 4i), (10 + 1i), (10 + 3i), (8 + 7i), (11 + 0i), (11 + 4i), (10 + 7i), (11 + 6i), (13 + 2i), (10 + 9i), (12 + 7i), (14 + 1i), (15 + 2i), (13 + 8i), (15 + 4i), (16 + 1i), (13 + 10i), (14 + 9i), (16 + 5i), (17 + 2i), (13 + 12i), (14 + 11i), (16 + 9i), (18 + 5i), (17 + 8i), (19 + 0i), (18 + 7i), (17 + 10i), (19 + 6i), (20 + 1i), (20 + 3i), (15 + 14i), (17 + 12i), (20 + 7i), (21 + 4i), (19 + 10i), (22 + 5i), (20 + 11i), (23 + 0i), (21 + 10i), (19 + 14i), (20 + 13i), (24 + 1i), (23 + 8i), (24 + 5i), (18 + 17i), (19 + 16i), (25 + 4i), (22 + 13i), (25 + 6i), (23 + 12i), (26 + 1i), (26 + 5i), (22 + 15i), (27 + 2i), (26 + 9i), (20 + 19i), (25 + 12i), (22 + 17i), (26 + 11i), (28 + 5i), (25 + 14i), (27 + 10i), (23 + 18i), (29 + 4i), (29 + 6i), (25 + 16i), (23 + 20i), (24 + 19i), (29 + 10i), (28 + 13i), (31 + 0i), (31 + 4i), (31 + 6i).

This list is included for reference because there doesn’t seem to exist a similar list elsewhere on the web. All these primes a + bi are in the first quadrant (i.e. a > 0 and b ≥ 0) and have ab. They are listed in order of ascending norm, then ascending argument. (“Norm” means squared absolute value.)

For each prime, a set of symmetrical primes have been excluded from the list: If z = a + bi is prime, then so are −z, iz, −iz, z (conjugate), −z, iz, −iz, and b + ai (equal to iz). For example, 3 is prime, therefore so are −3, 3i, and −3i. For example, 5 + 2i is prime, therefore so are 5 − 2i, −5 + 2i, −5 − 2i, 2 + 5i, 2 − 5i, −2 + 5i, and −2 − 5i.

More info