is_gaussian_prime(z)?

Question

Task

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)

Answer 1

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

Answer 2

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:

Answer 3

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.

{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

Answer 4

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]
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

Answer 5

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|n`mod`a<1=a:2%(n`div`a)|1>0=(a+1)%n
0#b=2%d==[d]&&d`mod`4==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

Answer 6

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

Answer 7

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

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.

Answer 8

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.

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

Answer 9

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  

Answer 10

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

Answer 11

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:

Answer 12

Ruby -rprime, 65 60 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!

Answer 13

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