# is_gaussian_prime(z)?

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

## Definition:

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 (mod 4)
• b is zero, |a| is prime and |a| = 3 (mod 4)

## Details

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

Some larger primes:

(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)

• Are we allowed to use factorisation functions (factor in Bash, mf and mF in CJam, ...) – user16402 Aug 7 '14 at 16:24
• 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. – flawr Aug 7 '14 at 16:36
• 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. – undergroundmonorail Aug 7 '14 at 20:31
• Thats nice, I originally just didn't want to directly point out how to determine the primality in order for people to get creative=) – flawr Aug 7 '14 at 22:31
• 1 1073741857 not seems to me a Gaussian prime because 1^2+ 1073741857^2 is one even number... – RosLuP Oct 19 '19 at 20:45

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)
0%a=a%0
a%b=p$a^2+b^2  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) 0%a=a%0 a%b=p$a*a+b*b


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.

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

## 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));}


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:

• +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=) – flawr Aug 8 '14 at 12:46
• 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++;); – Alchymist Aug 16 '14 at 22:20
• @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? – Todd Lehman Aug 16 '14 at 23:09
• 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. – Alchymist Aug 21 '14 at 22:29
• 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. – feersum Aug 21 '14 at 22:35

# APL (Dyalog Unicode), 364748494743 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.

{2=≢∪⍵∨⍳⍵}|+.×0∘∊⊃|{⍺⍵}3=4||


Try it online!

### Explanation

{2=≢∪⍵∨⍳⍵}|+.×0∘∊⊃|{⍺⍵}3=4||

|  ⍝ 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.

a%1=[]
a%n|nmoda<1=a:2%(ndiva)|1>0=(a+1)%n
0#b=2%d==[d]&&dmod4==3where d=abs(b)
a#0=0#a
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.

*Main>1#1
True
*Main>(-3)#0
True
*Main>2#2
False


# 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

• Glad I could help :) – killmous Aug 7 '14 at 19:55
• 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. – Peter Taylor Aug 7 '14 at 21:28
• @PeterTaylor Thank you for pointing out the bug... – hlt Aug 7 '14 at 21:44
• Calling f(0,15) yields TypeError: unsupported operand type(s) for &: 'bool' and 'generator' with my interpreter. :( – Falko Aug 9 '14 at 18:58
• f(0,15) gives False for me, both on 2.7.6 and 3.4.1 (on OS X). What version are you on? – hlt Aug 9 '14 at 21:45

# Python 2.7, 341301 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]
r=[2]
#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

• 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 – Jo King Nov 18 '19 at 8:30
• (15,0) is now true in 257 bytes version and the run time increased too 5.5s, sorry – Alexey Burdin Nov 18 '19 at 9:14

# Perl - 110107 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)}


Ungolfed:

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.

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

# golflua147 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.

\p(x)s=2@s*s<=M.a(x)?(x%s==0)~0$s=s+1$~1$\g(a,b)?a*b!=0~p(a^2+b^2)??a==0~p(b)+M.a(b)%4>2??b==0~p(a)+M.a(a)%4>2!?~0$$w(g(tn(I.r()),tn(I.r())))  Returns 1 if true and 0 if not. An ungolfed Lua version, -- prime number checker function p(x) s=2 while s*s<=math.abs(x) do if(x%s==0) then return 0 end s=s+1 end return 1 end -- 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 else return 0 end end a=tonumber(io.read()) b=tonumber(io.read()) print(g(a,b))  • 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 – mniip Aug 8 '14 at 4:06 • @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! – Kyle Kanos Aug 8 '14 at 10:52 • 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). – flawr Aug 8 '14 at 15:01 • @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. – Kyle Kanos Aug 8 '14 at 15:09 • @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! – Kyle Kanos Aug 8 '14 at 19:41 # APL(NARS), 99 chars, 198 bytes r←p w;i;k r←0⋄→0×⍳w<2⋄i←2⋄k←√w⋄→3 →0×⍳0=i∣w⋄i+←1 →2×⍳i≤k r←1 f←{v←√k←+/2*⍨⍺⍵⋄0=⍺×⍵:(p v)∧3=4∣v⋄p k}  test:  0 f 13 0 0 f 9 0 2 f 3 1 3 f 4 0 0 f 7 1 0 f 9 0 4600 f 5603 1  # Runic Enchantments, 41 bytes >ii:0)?\S:0)?\:*S:*+'PA@ 3%4A|'S/;$=?4/?3


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:

>ii:0)?\S:0)?\:*S:*+'PA@
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

If[a==0,#[[3]]&&Mod[Abs@b,4]==3,If[b==0,#[[2]]&&Mod[Abs@a,4]==3,#[[1]]]]&[(q=#;Total[Boole@IntegerQ[q/#]&/@Range@q]<3&&q!=0)&/@{a^2+b^2,Abs@a,Abs@b}]


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:

# Ruby-rprime, 6560 80 bytes

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

->a,b{r=->n{(2...n).all?{|i|n%i>0}};c=(a+b).abs;r[a*a+b*b]||a*b==0&&r[c]&&c%4>2}


Try it online!

# Python - 117 122 121

def f(a,b):
v=(a**2+b**2,a+b)[a*b==0]
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

• Because 3 is the largest a number can be mod 4, you could replace the ==3 with >2 – FlipTack Oct 19 '19 at 11:27