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.
a + bi is a Gaussian prime if and only if it meets one of the following conditions:
bare both nonzero and
a^2 + b^2is prime
|b|is prime and
|b| = 3 (mod 4)
|a|is prime and
|a| = 3 (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
factor. The lowest number of bytes wins. The program must work for
a^2+b^2 is a 32bit (signed) integer and should finish in not significantly more than 30 sec. I highly discurage bruteforcing (boring).
The dots represent prime numbers on the gaussian plane (x = real, y = imaginary axis):
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']