Write a function that accepts two integers \$a,b\$ that represent the Gaussian integer \$z = a+bi\$ (complex number). The program must return true or false depending on whether \$a+bi\$ is a Gaussian prime or not.


\$a+bi\$ is a Gaussian prime if and only if it meets one of the following conditions:

  • \$a\$ and \$b\$ are both nonzero and \$a^2 + b^2\$ is prime
  • \$a\$ is zero, \$|b|\$ is prime and \$|b| = 3 \text{ (mod }4)\$
  • \$b\$ is zero, \$|a|\$ is prime and \$|a| = 3 \text{ (mod }4)\$


You should only write a function. If your language does not have functions, you can assume that the integers are stored in two variables and print the result or write it to a file.

You cannot use built-in functions of your language like isprime or prime_list or nthprime or factor. The lowest number of bytes wins. The program must work for \$a,b\$ where \$a^2+b^2\$ is a 32bit (signed) integer and should finish in not significantly more than 30 seconds.

Prime list

The dots represent prime numbers on the Gaussian plane (x = real, y = imaginary axis):

enter image description here

Some larger primes:

(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)
  • 2
    \$\begingroup\$ Are we allowed to use factorisation functions (factor in Bash, mf and mF in CJam, ...) \$\endgroup\$
    – user16402
    Aug 7, 2014 at 16:24
  • \$\begingroup\$ Oh no, I forgot those factorizing methods existed, no please not=) And 32bit limit applies to a^2+b^2, would not make sense otherwise. Thank you for your inputs! I updated the question. \$\endgroup\$
    – flawr
    Aug 7, 2014 at 16:36
  • 2
    \$\begingroup\$ I added a definition of Gaussian primes to the post. If you don't like how I've done it, feel free to roll it back, but I would definitely recommend including the definition somewhere. \$\endgroup\$ Aug 7, 2014 at 20:31
  • \$\begingroup\$ Thats nice, I originally just didn't want to directly point out how to determine the primality in order for people to get creative=) \$\endgroup\$
    – flawr
    Aug 7, 2014 at 22:31
  • \$\begingroup\$ 1 1073741857 not seems to me a Gaussian prime because 1^2+ 1073741857^2 is one even number... \$\endgroup\$
    – user58988
    Oct 19, 2019 at 20:45

16 Answers 16


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&&n%d;d++);return n/d/d|n<2?0:(a+b&3)>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<2 hidden in the return value calculation. This golfed code also makes use of a*b as a substitute for a&&b (in other words a!=0 && 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>=1, which is an overflow-safe way of saying n>=d*d or d*d<=n or in essence d<=sqrt(n).

Original version (149 characters):

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


  • 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:


  • 2
    \$\begingroup\$ +1 for the image! Could you also do one about the same size just in the first quadrant (because symmetry), it really looks great here=) \$\endgroup\$
    – flawr
    Aug 8, 2014 at 12:46
  • \$\begingroup\$ You can save a couple of characters by replacing d=2;for(;n/d/d&&n%d;d++); with for(d=2;n/d/d&&n%d++;); \$\endgroup\$
    – Alchymist
    Aug 16, 2014 at 22:20
  • \$\begingroup\$ @Alchymist — That indeed saves characters, but produces incorrect results. It's important that the d++ not happen as part of the condition, else it messes up the logic following. Also, moving the d=2 inside the for loop actually increases the character count rather than decreasing it, because d still needs to be declared as int prior to the for loop. Am I missing something? \$\endgroup\$ Aug 16, 2014 at 23:09
  • \$\begingroup\$ Too true. Perils of looking at this away from a coding environment and not closely enough. Incrementing has to stay where it is and the initialisation only helps your original solution. There are obvious savings if you declare n & d outside the function, without specifying int, and initialise them in the for loop but I assume you are making the function self-contained which is a strict interpretation of the requirements. \$\endgroup\$
    – Alchymist
    Aug 21, 2014 at 22:29
  • 1
    \$\begingroup\$ The prime-testing loop here is some spectacular golfing! However it is possible to achieve even more savings by dropping the int type specifiers for the return type and arguments, using a variable for |a| + |b| and optimizing the return statement: G(a,b){int s=abs(a)+abs(b),n=a*b?a*a+b*b:s,d=2;for(;n/d/d&&n%d;d++);return n>1>n/d/d&&s%4/3|a*b;} comes out to just 97 characters. \$\endgroup\$
    – feersum
    Aug 21, 2014 at 22:35

Haskell - 77/108107 Chars

usage: in both the solutions, typing a%b will return whether a+bi is a gaussian prime.

the lowest i managed, but no creativity or performance (77 chars)

p n=all(\x->rem n x>0)[2..n-1]
a%0=rem a 4==3&&p(abs a)

this solution just powers through all numbers below n to check if it's prime.

ungolfed version:

isprime = all (\x -> rem n x != 0) [2..n-1] -- none of the numbers between 2 and n-1 divide n.
isGaussianPrime a 0 = rem a 4==3 && isprime (abs a)
isGaussianPrime 0 a = isGaussianPrime a 0   -- the definition is symmetric
isGaussianPrime a b = isprime (a^2 + b^2)

the next solution has an extra feature - memoization. once you checked if some integer n is prime, you won't need to recalculate the "primeness" of all numbers smaller than or equal to n, as it will be stored in the computer.

(107 chars. the comments are for clarity)

s(p:x)=p:s[n|n<-x,rem n p>0] --the sieve function
l=s[2..]                     --infinite list of primes
p n=n==filter(>=n)l!!0       --check whether n is in the list of primes
a%0=rem a 4==3&&p(abs a)

ungolfed version:

primes = sieve [2..] where
    sieve (p:xs) = p:filter (\n -> rem n p /= 0) xs
isprime n = n == head (filter (>=n) primes) -- checks if the first prime >= n is equal to n. if it is, n is prime.
isGaussianPrime a 0 = rem a 4==3 && isprime (abs a)
isGaussianPrime 0 a = isGaussianPrime a 0   -- the definition is symmetric
isGaussianPrime a b = isprime (a^2 + b^2)

this uses the sieve of Eratosthenes to compute an infinite list of all primes (called l for list in the code). (infinite lists are a well known trick of haskell).

how is it possible to have an infinite list? at the start of the program, the list is unevaluated, and instead of storing the lists elements, the computer stores the way to compute them. but as the program accesses the list it partially evaluates itself up to the request. so, if the program were to request the fourth item in the list, the computer would compute all primes up to the forth that aren't already evaluated, store them, and the rest would remain unevaluated, stored as the way to compute them once needed.

note that all of this is given freely by the lazy nature of the Haskell language, none of that is apparent from the code itself.

both versions of the program are overloaded, so they can handle arbitrarily-sized data.

  • \$\begingroup\$ By my count, your first solution is actually 77 characters :D \$\endgroup\$
    – killmous
    Aug 7, 2014 at 20:32
  • \$\begingroup\$ i counted newlines, shouldn't i? \$\endgroup\$ Aug 7, 2014 at 20:34
  • \$\begingroup\$ I count 74 regular characters and 3 newlines \$\endgroup\$
    – killmous
    Aug 7, 2014 at 20:35
  • \$\begingroup\$ you're right, it seems that for some reason notepad++ adds characters before newlines. thanks! \$\endgroup\$ Aug 7, 2014 at 20:39
  • \$\begingroup\$ that's why I use sublime ;) glad to help! \$\endgroup\$
    – killmous
    Aug 7, 2014 at 20:40

APL (Dyalog Unicode), 36 47 48 49 47 43 28 bytes

Takes an array of two integers a b and returns the Boolean value of the statement a+bi is a Gaussian integer.

Edit: +11 bytes because I misunderstood the definition of a Gaussian prime. +1 byte from correcting the answer again. +1 byte from a third bug fix. -2 bytes due to using a train instead of a dfn. -4 bytes thanks to ngn due to using a guard condition: if_true ⋄ if_false instead of if_true⊣⍣condition⊢if_false. -15 bytes thanks to ngn due to finding a completely different way to write the condition-if-else as a full train.


Try it online!



                           |  ⍝ abs(a), abs(b) or abs(list)
                       3=4|   ⍝ Check if a and b are congruent to 3 (mod 4)
                  |{⍺⍵}       ⍝ Combine with (abs(a), abs(b))
              0∘∊⊃            ⍝ Pick out the original abs(list) if both are non-zero
                              ⍝ Else pick out (if 3 mod 4)
          |+.×                ⍝ Dot product with abs(list) returns any of
                              ⍝ - All zeroes if neither check passed
                              ⍝ - The zero and the number that IS 3 mod 4
                              ⍝ - a^2 + b^2
{2=≢∪⍵∨⍳⍵}                    ⍝ Check if any of the above are prime, and return

Haskell -- 121 chars (newlines included)

Here's a relatively simple Haskell solution that doesn't use any external modules and is golfed down as much as I could get it.

0#b=2%d==[d]&&d`mod`4==3where d=abs(b)
a#b=2%c==[c]where c=a^2+b^2

Invoke as ghci ./gprimes.hs and then you can use it in the interactive shell. Note: negative numbers are finicky and must be placed in parentheses. I.e.


Python - 121 120 chars

def p(x,s=2):
 while s*s<=abs(x):yield x%s;s+=1
f=lambda a,b:(all(p(a*a+b*b))if b else f(b,a))if a else(b%4>2)&all(p(b))

p checks whether abs(x) is prime by iterating over all numbers from 2 to abs(x)**.5 (which is sqrt(abs(x))). It does so by yielding x % s for each s. all then checks whether all the yielded values are non-zero and stops generating values once it encounters a divisor of x. In f, f(b,a) replaces the case for b==0, inspired by @killmous' Haskell answer.

-1 char and bugfix from @PeterTaylor

  • \$\begingroup\$ Glad I could help :) \$\endgroup\$
    – killmous
    Aug 7, 2014 at 19:55
  • \$\begingroup\$ You could replace s<abs(x)**.5 with s*s<abs(x) for a saving of 2. Although really you should be checking <=, so it's probably buggy at present. \$\endgroup\$ Aug 7, 2014 at 21:28
  • \$\begingroup\$ @PeterTaylor Thank you for pointing out the bug... \$\endgroup\$
    – hlt
    Aug 7, 2014 at 21:44
  • \$\begingroup\$ Calling f(0,15) yields TypeError: unsupported operand type(s) for &: 'bool' and 'generator' with my interpreter. :( \$\endgroup\$
    – Falko
    Aug 9, 2014 at 18:58
  • \$\begingroup\$ f(0,15) gives False for me, both on 2.7.6 and 3.4.1 (on OS X). What version are you on? \$\endgroup\$
    – hlt
    Aug 9, 2014 at 21:45

Python 2.7, 341 301 253 bytes, optimized for speed

lambda x,y:(x==0and g(y))or(y==0and g(x))or(x*y and p(x*x+y*y))
def p(n,r=[2]):a=lambda n:r+range(r[-1],int(n**.5)+1);r+=[i for i in a(n)if all(i%j for j in a(i))]if n>r[-1]**2else[];return all(n%i for i in r if i*i<n)
g=lambda x:abs(x)%4>2and p(abs(x))

Try it online!

#pRimes. need at least one for r[-1]
#list of primes and other to-check-for-primarity numbers 
#(between max(r) and sqrt(n))
a=lambda n:r+list(range(r[-1],int(n**.5)+1))
#is_prime, using a(n)
f=lambda n:all(n%i for i in a(n))
#is_prime, using r
def p(n):
    global r
    #if r is not enough, update r
    if n>r[-1]**2:
        r+=[i for i in a(n) if f(i)]
    return all(n%i for i in r if i*i<n)
#sub-function for testing (0,y) and (x,0)
g=lambda x:abs(x)%4==3 and p(abs(x))
#the testing function
h=lambda x,y:(x==0 and g(y)) or (y==0 and g(x)) or (x and y and p(x*x+y*y))

Thanks: 40+48 -- entire golfing to Jo King

  • \$\begingroup\$ The f lambda is also uneccesary, along with the list call. 257 bytes without those, plus some whitespace removal. This perhaps isn't as efficient anymore though \$\endgroup\$
    – Jo King
    Nov 18, 2019 at 8:30
  • \$\begingroup\$ (15,0) is now true in 257 bytes version and the run time increased too 5.5s, sorry \$\endgroup\$ Nov 18, 2019 at 9:14

Perl - 110 107 105 chars

I hope I followed the linked definition correctly...

sub f{($a,$b)=map abs,@_;$n=$a**(1+!!$b)+$b**(1+!!$a);(grep{$n%$_<1}2..$n)<2&&($a||$b%4>2)&&($b||$a%4>2)}


sub f {
  ($a,$b) = map abs, @_;
  $n = $a**(1+!!$b) + $b**(1+!!$a);
  (grep {$n%$_<1} 2..$n)<2 && ($a || $b%4==3) && ($b || $a%4==3)

Explanation, because someone asked: I read the arguments (@_) and put their absolute values into $a,$b, because the function does not need their sign. Each of the criteria requires testing a number's primality, but this number depends on whether $a or $b are zero, which I tried to express in the shortest way and put in $n. Finally I check whether $n is prime by counting how many numbers between 2 and itself divide it without a remainder (that's the grep...<2 part), and then check in addition that if one of the numbers is zero then the other one equals 3 modulo 4. The function's return value is by default the value of its last line, and these conditions return some truthy value if all conditions were met.

  • \$\begingroup\$ I can't get it to work for negative parameters. \$\endgroup\$
    – killmous
    Aug 7, 2014 at 20:31
  • 1
    \$\begingroup\$ @killmous you're right, just fixed it \$\endgroup\$
    – Tal
    Aug 7, 2014 at 20:33
  • \$\begingroup\$ may you explain the algorithm? \$\endgroup\$ Aug 7, 2014 at 22:03
  • 1
    \$\begingroup\$ Nice! By the way, I think you could shave off a couple characters by writing $a%4>2 instead of $a%4==3. \$\endgroup\$ Aug 7, 2014 at 23:01

golflua 147 141

The above count neglects the newlines that I've added to see the different functions. Despite the insistence to not do so, I brute-force solve primes within the cases.


Returns 1 if true and 0 if not.

An ungolfed Lua version,

-- prime number checker
function p(x)
   while s*s<=math.abs(x) do
      if(x%s==0) then return 0 end
   return 1

-- check gaussian primes
function g(a,b)
   if a*b~=0 then
      return p(a^2+b^2)
   elseif a==0 then
      return p(b) + math.abs(b)%4>2
   elseif b==0 then
      return p(a) + math.abs(a)%4>2
      return 0

  • \$\begingroup\$ You can save 6 characters by just plugging tonumber(io.read()) as an argument to g in the end, and 2 more by removing the newlines \$\endgroup\$
    – mniip
    Aug 8, 2014 at 4:06
  • \$\begingroup\$ @mniip: the newlines were not counted, I just added those in for clarity (no sideways scrolling). I'll update the read in g when I get into work in a little bit. Thanks! \$\endgroup\$
    – Kyle Kanos
    Aug 8, 2014 at 10:52
  • \$\begingroup\$ Well does it still work in a reasonable amout of time for large numbers? I primarly thought about bruteforcing in the way of checking all gaussian integers a where |a| <= |z| if a | z (if a divides z). \$\endgroup\$
    – flawr
    Aug 8, 2014 at 15:01
  • \$\begingroup\$ @flawr: I tested it with a=2147483644, b=896234511 and got 0 in about 0.002 s. I also tested it with 2147483629 & 2147483587 (two very large primes) and got 0 in another 0.002 s. I'm trying to find a large pair of numbers such that a^2+b^2 is prime & ensure that I've got a working solution for such large numbers. \$\endgroup\$
    – Kyle Kanos
    Aug 8, 2014 at 15:09
  • \$\begingroup\$ @flawr: Tested with a=4600 & b=5603 (a^2+b^2=2147393609 is prime & < 2^32-1) and it took the same 0.002 seconds to return 1. Yay! \$\endgroup\$
    – Kyle Kanos
    Aug 8, 2014 at 19:41

APL(NARS), 99 chars, 198 bytes

r←p w;i;k

f←{v←√k←+/2*⍨⍺⍵⋄0=⍺×⍵:(p v)∧3=4∣v⋄p k}


  0 f 13
  0 f 9
  2 f 3
  3 f 4
  0 f 7
  0 f 9
  4600 f 5603

Runic Enchantments, 41 bytes


Try it online!

Ended up being a lot easier than I thought and wasn't much room for golfification. The original program I blocked out was:

3%4A|'S/!   S/;$=

I played around with trying to compare both inputs at the same time (which saved all of one 1 byte), but when that drops into the "one of them is zero" section, there wasn't a good way to figure out which item was non-zero in order to perform the last check, much less a way to do it without spending at least 1 byte (no overall savings).


Mathematica, 149 Characters


The code doesn't use any standard prime number features of mathematica, instead it counts the number of integers in the list {n/1,n/2,...,n/n}; if the number is 1 or 2, then n is prime. An elaborated form of the function:

MyIsPrime[p_] := (q = Abs@p; 
  Total[Boole@IntegerQ[q/#] & /@ Range@q] < 3 && q != 0)

Bonus plot of all the Gaussian Primes from -20 to 20:

Plot of gaussian primes


Ruby -rprime, 65 60 80 bytes

Didn't notice the "can't use isPrime" rule...


Try it online!


Uiua, 24 bytes


Try it online!

Straightforward implementation of the condition described on the Mathworld page.

=1/+=0◿⇡./+×⍥(=3◿4)∊0..⌵   input: a 2-element vector [a b] representing a+bi
                         ⌵   absolute value of each
             ⍥(    )∊0..    on a copy of it, if it contains 0,
                =3◿4        change it to v%4==3
          /+×                elementwise multiply and sum
                             (gives a^2+b^2 if ab!=0, a or b if it is 3 mod 4 and
                             the other is 0, 0 otherwise)
=1/+=0◿⇡.                    primality test

JavaScript (Node.js), 78 bytes


Try it online!

JavaScript (Node.js), 93 bytes, slow


Try it online!

Modified from vanilla definition of Gaussian prime: there's exactly 8 pairs of complex <x,y>, s.t. x*y=input


Vyxal, 136 bitsv2, 17 bytes


Try it Online!



Literal interpretation of mathworld


Python - 117 122 121

def f(a,b):
 for i in range(2,abs(v)):
  if v%i<1:a=b=0
 return abs((a,b)[a==0])%4==3or a*b!=0
  • \$\begingroup\$ Because 3 is the largest a number can be mod 4, you could replace the ==3 with >2 \$\endgroup\$
    – FlipTack
    Oct 19, 2019 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.