3361专题

poj 3361 Gaussian Prime Factors 高斯素数约数

poj 3361 Gaussian Prime Factors 题意: 在复数 a+bj (a,b为整数)范围内,约数只有 1, -1, a+bj, -(a+bj)的称为高斯素数。求任给正整数N的所有素因子(|b|>a>0)。默认N<2e9 解法: 定理有云: n≡3(mod 4)者,无因式分解。 n≡1(mod 4)者,可唯一分解为两个共轭高斯整数乘积。 当然做的时候并不知道!