## 原始题面

### Description

Let $$a, b, c, d$$ be integers. The complex number $$a+bj$$, where $$j^2 = -1$$, is a factor of $$c+dj$$, if there exist integers $$e$$ and $$f$$ such that

$$c + dj = (a + bj)(e + fj)$$

A complex number $$a + bj$$ where $$a$$ and $$b$$ are integers is a Gaussian prime if the factors are $$1, -1, -a - bj$$ and $$a + bj$$ only

The following are Gaussian primes: $$1 + j, 1 - j, 1 + 2j, 1 - 2j, 3$$ and $$7$$

The Gaussian prime factors of 5 are:

$$1 + 2j$$ and $$1 - 2j$$, or
$$2 + j$$ and $$2 - j$$, or
$$-1 - 2j$$ and $$-1 + 2j$$, or
$$-2 - j$$ and $$-2 + j$$

Write a program that finds all the Gaussian prime factors of a positive integer

### Input

One line of input per case. The line represents a positive integer $$n$$

### Output

One line of output per test case. The line represents the Gaussian prime factors of $$n$$. If $$a + bj$$ is a Gaussian prime factor of $$n$$, then $$a > 0$$, $$|b| ≥ a$$, if $$b ≠ 0$$. If $$b = 0$$, the output must be $$a$$

### Hint

Output the Gaussian prime factors in ascending order of $$a$$. If there are more than one factors with the same $$a$$, output them in ascending order of $$b$$ by absolute value. If two conjugate factors coexist, the one with a positive imaginary part precedes that with a negative imaginary part

Manila 2006

## 解题思路

• 首先对 $$s$$ 做质因数分解
• 其次考察 $$s$$ 的每个质因子 $$p$$
• $$p\equiv 3\pmod4$$, 说明 $$p$$ 不能表示成二平方和的形式，故 $$p$$ 也是 $$\mathbb{Z}[j]$$ 下的素数 (即 Gauss 素数)
• $$p\equiv 1\pmod4$$, 说明 $$p$$ 能表示成二平方和的形式，设 $$p=a^2+b^2$$$$a+bi,~a-bi$$ 是 Gauss 素数而 $$p$$ 不是

Show code