問題描述：
求一個整數(shù)的高斯素因子。
解題思路：
高斯整數(shù)
a + bi是素數(shù)當且僅當：
1)a、b中有一個是零，另一個數(shù)的絕對值是形如
4n + 3的素數(shù)；
2)a、b均不為零，而
a2 + b2為素數(shù)；
于是只要將每個分解素因子，對于每個素因子P,如果該素因子形如4n+3，則必定能分解成(a+bj)(a-bj) = a^2 + b^2，枚舉解決。
代碼如下：
#include <iostream>
#include <cmath>
using namespace std;
int f[65537], p[65537], size;
int pri[1000], top;
int n;
struct point
{
int a;
int b;
char oper;
}s[10000];
int num;
//篩選素數(shù)
void init()
{
f[1] = 1;
int i, j;
for(i = 2; i <= 65536; i++)
{
if(!f[i])
{
p[ size++ ] = i;
for(j = i+i; j <= 65536; j += i)
f[j] = 1;
}
}
}
//素因子分解
void Flip(int key)
{
int i;
top = 0;
for(i = 0; i < size; i++)
{
if(key % p[i] == 0)
{
pri[ top++ ] = p[i];
key /= p[i];
while(key % p[i] == 0){
pri[ top++ ] = p[i];
key /= p[i];
}
}
}
if(key - 1)
pri[ top++ ] = key;
}
//高斯素數(shù)分解
void Part(int prime)
{
int i;
if(prime == 2)
{
s[ num ].a = 1; s[ num ].b = 1; s[ num++ ].oper = '+';
s[ num ].a = 1; s[ num ].b = 1; s[ num++ ].oper = '-';
}else if( (prime - 1) % 4 == 0)
{
for(i = 1; ;i++)
{
int u = int(sqrt(prime - i*i*1.0) + 1e-5);
if(u*u + i*i == prime)
{
s[ num ].a = i; s[ num ].b = u; s[ num++ ].oper = '+';
s[ num ].a = i; s[ num ].b = u; s[ num++ ].oper = '-';
break;
}
}
}else
{
s[ num ].a = prime; s[ num++ ].b = 0;
}
}
int cmp(const void *a, const void *b)
{
point *c = (point *)a;
point *d = (point *)b;
if(c->a != d->a)
return c->a - d->a;
if(c->b != d->b)
return c->b - d->b;
return c->oper == '-' ? 1 : -1;
}
void Print(int key)
{
printf("%d", s[key].a );
if(s[key].b == 0)
return;
if(s[key].b == 1)
{
printf("%cj", s[key].oper);
}else
{
printf("%c%dj", s[key].oper, s[key].b);
}
}
int main()
{
init();
int i, cas = 1;
while(scanf("%d", &n) != EOF)
{
num = 0;
Flip(n);
for(i = 0; i < top; i++)
{
Part(pri[i]);
}
qsort(s, num, sizeof(point), cmp);
printf("Case #%d: ", cas++);
Print(0);
for(i = 1; i < num; i++)
{
if(s[i].a == s[i-1].a
&& s[i].b == s[i-1].b
&& s[i].oper == s[i-1].oper)
continue;
if(i)
printf(", ");
Print(i);
}
puts("");
}
}