Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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 sec. I highly discurage bruteforcing (boring).

Prime list

The dots represent prime numbers on the gaussian plane (x = real, y = imaginary axis): enter image description here

UPDATE: I made a list of some big gaussion primes (code below):

 6   1073741833
 1   1073741857
 5   1073741909
11   1073741953
10   1073741969
 7   1073741993
 5   1073742037
 5   1073742053
 4   1073742073
 7   1073742077
11   1073742113
 2   1073742169
 7   1073742209

Made by using this code (Matlab):

p  = [];
for x = (2^30+1):4:(2^30+10000)
    if isprime(x)
        p = [p,x];
    end
end
x = []; y = [];
for q = p
    for xx = randperm(q);
        if mod(sqrt(q^2-xx^2),1) == 0
            x = [x,xx];
            y = [y,sqrt(q^2-xx^2)];
            break;
        end
    end
end
x.^2+y.^2 == p.^2
[x',y']
share|improve this question
2  
Are we allowed to use factorisation functions (factor in Bash, mf and mF in CJam, ...) –  professorfish Aug 7 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 at 16:36
2  
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 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 at 22:31

7 Answers 7

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:

Sample128

share|improve this answer
1  
+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 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 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 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 at 22:29
1  
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 at 22:35

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
share|improve this answer

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.

share|improve this answer
    
I can't get it to work for negative parameters. –  killmous Aug 7 at 20:31
1  
@killmous you're right, just fixed it –  Tal Aug 7 at 20:33
    
may you explain the algorithm? –  proud haskeller Aug 7 at 22:03
1  
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 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.

\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))
share|improve this answer
    
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 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 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 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 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 at 19:41

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

share|improve this answer
    
Glad I could help :) –  killmous Aug 7 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 at 21:28
    
@PeterTaylor Thank you for pointing out the bug... –  hlt Aug 7 at 21:44
    
Calling f(0,15) yields TypeError: unsupported operand type(s) for &: 'bool' and 'generator' with my interpreter. :( –  Falko Aug 9 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 at 21:45

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.

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

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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