is_gaussian_prime(z)?
C, 149 118 characters

Edited version (118 characters):

int G(int a,int b){a=abs(a);b=abs(b);int n=a*b?a*a+b*b:a+b,
d=2;for(;n/d/d&amp;&amp;n%d;d++);return n/d/d|n&lt;2?0:(a+b&amp;3)&gt;2|a*b;}


This is a single function:


G(a,b) returns nonzero (true) if a+bi is a Gaussian prime, or zero (false) otherwise.


It folds the integer primality test into an expression n/d/d|n&lt;2 hidden in the return value calculation. This golfed code also makes use of a*b as a substitute for a&amp;&amp;b (in other words a!=0 &amp;&amp; b!=0) and other tricks involving operator precedence and integer division. For example n/d/d is a shorter way of saying n/d/d&gt;=1, which is an overflow-safe way of saying n&gt;=d*d or d*d&lt;=n or in essence d&lt;=sqrt(n).



Original version (149 characters):

int Q(int n){int d=2;for(;n/d/d&amp;&amp;n%d;d++);return n/d/d||n&lt;2;}
int G(int a,int b){a=abs(a);b=abs(b);return!((a|b%4&lt;3|Q(b))*(b|a%4&lt;3|Q(a))*Q(a*a+b*b));}


Functions:


Q(n) returns 0 (false) if n is prime, or 1 (true) if n is nonprime. It is a helper function for G(a,b).
G(a,b) returns 1 (true) if a+bi is a Gaussian prime, or 0 (false) otherwise.


Sample output (scaled up 200%) for |a|,|b| ≤ 128: