is_gaussian_prime (z)?

23

Tarea

Escriba una función que acepte dos enteros a,bque representen el entero gaussiano z = a+ib(número complejo). El programa debe devolver verdadero o falso dependiendo de si a+ibes un primo gaussiano o no .

Definición:

a + bi es una prima gaussiana si y solo si cumple una de las siguientes condiciones:

  • ay bson ambos distintos de cero y a^2 + b^2es primo
  • aes cero, |b|es primo y|b| = 3 (mod 4)
  • bes cero, |a|es primo y|a| = 3 (mod 4)

Detalles

Solo debes escribir una función. Si su idioma no tiene funciones, puede suponer que los enteros se almacenan en dos variables e imprimir el resultado o escribirlo en un archivo.

No puede utilizar las funciones integradas de su idioma como isprimeo prime_listo nthprimeo factor. El menor número de bytes gana. El programa de trabajo imprescindible para a,bdonde a^2+b^2es un número entero de 32 bits (firmado) y debe terminar en no mucho más de 30 segundos.

Lista principal

Los puntos representan números primos en el plano gaussiano ( x= real, y= eje imaginario):

ingrese la descripción de la imagen aquí

Algunos primos más grandes:

(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)
falla
fuente
2
¿Se nos permite usar funciones de factorización ( factoren Bash mfy mFen CJam, ...)
Oh no, olvidé que existían esos métodos de factorización, no, por favor no =) Y el límite de 32 bits se aplica a a ^ 2 + b ^ 2, de lo contrario no tendría sentido. Gracias por tus aportes! Actualicé la pregunta.
flawr
2
Agregué una definición de primos gaussianos a la publicación. Si no le gusta cómo lo hice, no dude en revertirlo, pero definitivamente recomendaría incluir la definición en alguna parte.
undergroundmonorail
Eso es bueno, originalmente no quería señalar directamente cómo determinar la originalidad para que las personas sean creativas =)
error
1 1073741857 no me parece un primo gaussiano porque 1 ^ 2 + 1073741857 ^ 2 es un número par ...
RosLuP

Respuestas:

4

Haskell - 77/ 108 107 Chars

uso: en ambas soluciones, escribir a% b devolverá si a + bi es un primo gaussiano.

el más bajo que logré, pero sin creatividad ni rendimiento (77 caracteres)

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

Esta solución solo funciona con todos los números debajo de n para verificar si es primo.

versión sin golf:

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)

La siguiente solución tiene una característica adicional: la memorización. una vez que haya verificado si algún número entero n es primo, no necesitará volver a calcular la "prima" de todos los números menores o iguales a n, ya que se almacenarán en la computadora.

(107 caracteres. Los comentarios son para mayor claridad)

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

versión sin golf:

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)

esto usa el tamiz de Eratóstenes para calcular una lista infinita de todos los números primos (llamada l para lista en el código). (Las listas infinitas son un truco bien conocido de Haskell).

¿Cómo es posible tener una lista infinita? al comienzo del programa, la lista no está evaluada y, en lugar de almacenar los elementos de la lista, la computadora almacena la forma de calcularlos. pero a medida que el programa accede a la lista, se evalúa parcialmente hasta la solicitud. por lo tanto, si el programa solicitara el cuarto elemento de la lista, la computadora calcularía todos los números primos hasta el cuarto que aún no se han evaluado, los almacenará, y el resto permanecerá sin evaluar, almacenados como la forma de calcularlos una vez necesario.

Tenga en cuenta que todo esto se da libremente por la naturaleza perezosa del lenguaje Haskell, nada de eso se desprende del código en sí.

ambas versiones del programa están sobrecargadas, por lo que pueden manejar datos de tamaño arbitrario.

orgulloso Haskeller
fuente
Según mi cuenta, su primera solución es en realidad 77 caracteres: D
killmous
Conté nuevas líneas, ¿no?
orgulloso Haskeller
Cuento 74 personajes regulares y 3 líneas nuevas
killmous
tienes razón, parece que por alguna razón notepad ++ agrega caracteres antes de las nuevas líneas. ¡Gracias!
orgulloso Haskeller
es por eso que uso sublime;) me alegro de ayudar!
killmous
9

C, 149 118 caracteres

Versión editada (118 caracteres):

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

Esta es una función única:

  • G ( a , b ) devuelve distinto de cero (verdadero) si a + bi es un primo gaussiano, o cero (falso) de lo contrario.

Dobla la prueba de primalidad entera en una expresión n/d/d|n<2oculta en el cálculo del valor de retorno. Este código de golf también se usa a*bcomo un sustituto a&&b(en otras palabras a!=0 && b!=0) y otros trucos que involucran la precedencia del operador y la división de enteros. Por ejemplo n/d/des una forma más corta de decir n/d/d>=1, que es una manera de desbordamiento de fallos de decir n>=d*do d*d<=nbien en su esencia d<=sqrt(n).


Versión original (149 caracteres):

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

Funciones:

  • Q ( n ) devuelve 0 (falso) si n es primo o 1 (verdadero) si n no es primo. Es una función auxiliar para G ( a , b ).

  • G ( a , b ) devuelve 1 (verdadero) si a + bi es un primo gaussiano, o 0 (falso) de lo contrario.

Salida de muestra (ampliada 200%) para | a |, | b | ≤ 128:

Muestra128

Todd Lehman
fuente
2
+1 para la imagen! ¿Podría también hacer uno del mismo tamaño solo en el primer cuadrante (porque la simetría), realmente se ve muy bien aquí =)
error
Puede guardar un par de caracteres reemplazando d = 2; for (; n / d / d && n% d; d ++); con for (d = 2; n / d / d && n% d ++;);
Alchymist
@Alchymist: eso realmente ahorra caracteres, pero produce resultados incorrectos. Es importante que d++no suceda como parte de la condición, de lo contrario, estropea la lógica siguiente. Además, mover el d=2interior del forbucle en realidad aumenta el recuento de caracteres en lugar de disminuirlo, ya que daún debe declararse como intanterior al forbucle. ¿Me estoy perdiendo de algo?
Todd Lehman
Demasiado cierto. Peligros de ver esto lejos de un entorno de codificación y no lo suficientemente cerca. El incremento tiene que permanecer donde está y la inicialización solo ayuda a su solución original. Hay ahorros obvios si declara n & d fuera de la función, sin especificar int e inicializándolos en el bucle for, pero supongo que está haciendo que la función sea autónoma, lo que es una interpretación estricta de los requisitos.
Alquimista
1
¡El circuito de prueba principal aquí es un golf espectacular! Sin embargo, es posible lograr aún más ahorros al soltar los especificadores de tipo int para el tipo de retorno y los argumentos, utilizando una variable para | a | + | b | y optimizando la declaración de retorno: 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;}sale a solo 97 caracteres.
Feersum
4

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

Toma una matriz de dos enteros a by devuelve el valor booleano de la declaración a+bi is a Gaussian integer.

Editar: +11 bytes porque no entendí la definición de un primer gaussiano. +1 byte al corregir la respuesta nuevamente. +1 byte de una tercera corrección de error. -2 bytes debido al uso de un tren en lugar de un dfn. -4 bytes gracias a ngn debido al uso de un protector en condition: if_true ⋄ if_falselugar de if_true⊣⍣condition⊢if_false. -15 bytes gracias a ngn debido a la búsqueda de una forma completamente diferente de escribir la condición if-else como un tren completo.

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

Pruébalo en línea!

Explicación

{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
Sherlock9
fuente
3

Haskell - 121 caracteres (nuevas líneas incluidas)

Aquí hay una solución de Haskell relativamente simple que no utiliza ningún módulo externo y se reduce al máximo todo lo que pude obtener.

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

Invoque como ghci ./gprimes.hsy luego puede usarlo en el shell interactivo. Nota: los números negativos son delicados y deben colocarse entre paréntesis. Es decir

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

Python - 121 120 caracteres

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

pcomprueba si abs(x)es primo iterando sobre todos los números del 2 al abs(x)**.5(que es sqrt(abs(x))). Lo hace cediendo x % spara cada uno s. allluego comprueba si todos los valores producidos son distintos de cero y deja de generar valores una vez que encuentra un divisor de x. En f, f(b,a)reemplaza el caso b==0, inspirado por la respuesta de Haskell de @killmous .


-1 char y corrección de errores de @PeterTaylor

hlt
fuente
Me alegro de poder ayudar :)
killmous
Se podría reemplazar s<abs(x)**.5con s*s<abs(x)un ahorro de 2. A pesar de que realmente debe ser la comprobación <=, por lo que es probable que con errores en la actualidad.
Peter Taylor
@PeterTaylor Gracias por señalar el error ...
hlt
Llamar f(0,15)cede TypeError: unsupported operand type(s) for &: 'bool' and 'generator'con mi intérprete. :(
Falko
f(0,15)da Falsepara mí, tanto en 2.7.6 y 3.4.1 (en OS X). ¿En que versión estas?
hlt
3

Python 2.7 , 341 301 253 bytes, optimizado para la velocidad

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

Pruébalo en línea!

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

Gracias: 40 +48 - golf completo a Jo King

Alexey Burdin
fuente
La flambda tampoco es necesaria, junto con la listllamada. 257 bytes sin esos, más la eliminación de algunos espacios en blanco. Sin embargo
Jo King el
(15,0) ahora es cierto en la versión de 257 bytes y el tiempo de ejecución aumentó también 5.5s, lo siento
Alexey Burdin
2

Perl - 110 107 105 caracteres

Espero haber seguido la definición vinculada correctamente ...

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

Sin golf:

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

Explicación, porque alguien le preguntó: He leído los argumentos ( @_) y poner en sus valores absolutos $a, $bporque la función no necesita su signo. Cada uno de los criterios requiere probar la primalidad de un número, pero este número depende de si es cero $ao $bno, lo que traté de expresar de la manera más corta y poner $n. Finalmente, verifico si $nes primo contando cuántos números entre 2 y sí mismo lo dividen sin residuo (esa es la grep...<2parte), y luego verifico además que si uno de los números es cero, el otro es igual a 3 módulo 4. La función El valor de retorno es por defecto el valor de su última línea, y estas condiciones devuelven algún valor verdadero si se cumplen todas las condiciones.

Tal
fuente
No puedo hacer que funcione para parámetros negativos.
killmous
1
@killmous tienes razón, solo lo arreglé
Tal
¿Puedes explicar el algoritmo?
orgulloso Haskeller
1
¡Agradable! Por cierto, creo que podrías eliminar un par de caracteres escribiendo en $a%4>2lugar de hacerlo $a%4==3.
Todd Lehman
2

golflua 147 141

El recuento anterior descuida las nuevas líneas que he agregado para ver las diferentes funciones. A pesar de la insistencia en no hacerlo, la fuerza bruta resuelve primos dentro de los casos.

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

Devuelve 1 si es verdadero y 0 si no.

Una versión de Lua sin golf,

-- 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))
Kyle Kanos
fuente
Puede guardar 6 caracteres simplemente conectando tonumber(io.read())como argumento al gfinal, y 2 más eliminando las nuevas líneas
mniip
@mniip: las nuevas líneas no se contaron, solo las agregué para mayor claridad (sin desplazamiento lateral). Actualizaré la lectura en g cuando empiece a trabajar en un momento. ¡Gracias!
Kyle Kanos
Bueno, ¿todavía funciona en un tiempo razonable para grandes números? Principalmente pensé en la fuerza bruta en la forma de verificar todos los enteros gaussianos adonde |a| <= |z|if a | z(if adivide z).
flawr
@flawr: Lo probé con a = 2147483644, b = 896234511 y obtuve 0 en aproximadamente 0.002 s. También lo probé con 2147483629 y 2147483587 (dos primos muy grandes) y obtuve 0 en otros 0.002 s. Estoy tratando de encontrar un gran número de números de modo que a ^ 2 + b ^ 2 sea primo y asegurarme de que tengo una solución que funcione para números tan grandes.
Kyle Kanos
@flawr: Probado con a = 4600 & b = 5603 (a ^ 2 + b ^ 2 = 2147393609 es primo & <2 ^ 32-1) y tardó los mismos 0,002 segundos en devolver 1. ¡Sí!
Kyle Kanos
1

APL (NARS), 99 caracteres, 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}

prueba:

  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  
RosLuP
fuente
1

Encantamientos rúnicos , 41 bytes

>ii:0)?\S:0)?\:*S:*+'PA@
3%4A|'S/;$=?4/?3

Pruébalo en línea!

Terminó siendo mucho más fácil de lo que pensaba y no había mucho espacio para la golfificación. El programa original que bloqueé fue:

>ii:0)?\S:0)?\:*S:*+'PA@
3%4A|'S/!   S/;$=

Jugué intentando comparar ambas entradas al mismo tiempo (lo que ahorró un 1 byte), pero cuando eso cae en la sección "uno de ellos es cero", no había una buena manera de averiguar qué elemento fue distinto de cero para realizar la última verificación, y mucho menos una forma de hacerlo sin gastar al menos 1 byte (sin ahorros generales).

Draco18s ya no confía en SE
fuente
1

Mathematica, 149 Personajes

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

El código no usa ninguna característica estándar de números primos de Mathica, en su lugar cuenta el número de enteros en la lista {n / 1, n / 2, ..., n / n}; si el número es 1 o 2, entonces n es primo. Una forma elaborada de la función:

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

Bonus plot de todos los Primes Gaussianos de -20 a 20:

Trama de primos gaussianos

ralian
fuente
1

Rubí -rprime , 65 60 80 bytes

No noté la regla "no se puede usar isPrime" ...

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

Pruébalo en línea!

Tinta de valor
fuente
0

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
Falko
fuente
Debido a que 3 es el número más grande que puede ser mod 4, puede reemplazarlo ==3con>2
FlipTack