找出高斯素数因子

"这篇文档是关于ACM竞赛中的一道问题——‘poj 3361 Gaussian Prime Factors’，涉及到数学与编程的结合，主要探讨了高斯素数（Gaussian Prime）的概念及其在因式分解中的应用。" 在这道问题中，你需要编写一个程序来找出一个正整数的所有高斯素数因子。高斯素数是在复数域中的素数概念，它具有形式a + bj，其中a和b是整数，并且j是虚数单位，满足j^2 = -1。一个高斯素数只有四个因子：1，-1，-a - bj以及a + bj。例如，1+j、1-j、1+2j、1-2j、3和7都是高斯素数。 题目提供了几个高斯素数的例子，并要求你的程序能处理不同的输入，输出相应的高斯素数因子。输入是一个正整数n，输出则是所有可能的高斯素数因子，按照a的升序排列。如果存在多个a相同的情况，则按照b的绝对值升序排列。如果存在共轭对（例如1+2j和1-2j），则优先输出虚部为正的那个。 例如，对于输入： ``` 2 5 6 700 ``` 对应的输出应为： ``` Case#1:1+j,1-j Case#2:1+2j,1-2j Case#3:1+j,1-j,3 Case#4:1+j,1-j,1+2j,1-2j,7 ``` 这表示2的高斯素数因子是1+j和1-j，5的因子是1+2j和1-2j，6的因子是1+j、1-j和3，而700的因子是1+j、1-j、1+2j、1-2j以及7。 解决这个问题的关键在于理解高斯素数的性质，以及如何有效地在复数域中进行因式分解。你可以采用试除法，尝试将输入的n除以所有的已知高斯素数，直到无法继续分解为止。或者，可以设计一个更高级的算法，如基于高斯整数模运算的算法，这通常会比简单的试除法更高效。 在编程实现时，需要注意的是，由于题目要求的输出格式，你需要维护一个有序的数据结构来存储找到的高斯素数因子，并确保在输出时按照题目要求的顺序进行。此外，对于高斯素数的检查，需要验证其唯一性，即检查它是否只能够被1和其自身整除。 这道题目结合了数论和编程的知识，对于参加ACM竞赛的选手来说，既是对数学理解的考验，也是对编程技巧的挑战。