Tarea
Escriba una función que acepte dos enteros a,b
que representen el entero gaussiano z = a+ib
(número complejo). El programa debe devolver verdadero o falso dependiendo de si a+ib
es un primo gaussiano o no .
Definición:
a + bi
es una prima gaussiana si y solo si cumple una de las siguientes condiciones:
a
yb
son ambos distintos de cero ya^2 + b^2
es primoa
es cero,|b|
es primo y|b| = 3 (mod 4)
b
es 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 isprime
o prime_list
o nthprime
o factor
. El menor número de bytes gana. El programa de trabajo imprescindible para a,b
donde a^2+b^2
es 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):
Algunos primos más grandes:
(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)
fuente
factor
en Bashmf
ymF
en CJam, ...)Respuestas:
Haskell - 77/
108107 Charsuso: 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)
Esta solución solo funciona con todos los números debajo de n para verificar si es primo.
versión sin golf:
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)
versión sin golf:
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.
fuente
C,
149118 caracteresVersión editada (118 caracteres):
Esta es una función única:
Dobla la prueba de primalidad entera en una expresión
n/d/d|n<2
oculta en el cálculo del valor de retorno. Este código de golf también se usaa*b
como un sustitutoa&&b
(en otras palabrasa!=0 && b!=0
) y otros trucos que involucran la precedencia del operador y la división de enteros. Por ejemplon/d/d
es una forma más corta de decirn/d/d>=1
, que es una manera de desbordamiento de fallos de decirn>=d*d
od*d<=n
bien en su esenciad<=sqrt(n)
.Versión original (149 caracteres):
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:
fuente
d++
no suceda como parte de la condición, de lo contrario, estropea la lógica siguiente. Además, mover eld=2
interior delfor
bucle en realidad aumenta el recuento de caracteres en lugar de disminuirlo, ya qued
aún debe declararse comoint
anterior alfor
bucle. ¿Me estoy perdiendo de algo?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.APL (Dyalog Unicode) ,
36474849474328 bytesToma una matriz de dos enteros
a b
y devuelve el valor booleano de la declaracióna+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_false
lugar deif_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.Pruébalo en línea!
Explicación
fuente
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.
Invoque como
ghci ./gprimes.hs
y luego puede usarlo en el shell interactivo. Nota: los números negativos son delicados y deben colocarse entre paréntesis. Es decirfuente
Python -
121120 caracteresp
comprueba siabs(x)
es primo iterando sobre todos los números del 2 alabs(x)**.5
(que essqrt(abs(x))
). Lo hace cediendox % s
para cada unos
.all
luego comprueba si todos los valores producidos son distintos de cero y deja de generar valores una vez que encuentra un divisor dex
. Enf
,f(b,a)
reemplaza el casob==0
, inspirado por la respuesta de Haskell de @killmous .-1 char y corrección de errores de @PeterTaylor
fuente
s<abs(x)**.5
cons*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.f(0,15)
cedeTypeError: unsupported operand type(s) for &: 'bool' and 'generator'
con mi intérprete. :(f(0,15)
daFalse
para mí, tanto en 2.7.6 y 3.4.1 (en OS X). ¿En que versión estas?Python 2.7 ,
341301253 bytes, optimizado para la velocidadPruébalo en línea!
Gracias: 40 +48 - golf completo a Jo King
fuente
f
lambda tampoco es necesaria, junto con lalist
llamada. 257 bytes sin esos, más la eliminación de algunos espacios en blanco. Sin embargoPerl -
110107105 caracteresEspero haber seguido la definición vinculada correctamente ...
Sin golf:
Explicación, porque alguien le preguntó: He leído los argumentos (
@_
) y poner en sus valores absolutos$a
,$b
porque 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$a
o$b
no, lo que traté de expresar de la manera más corta y poner$n
. Finalmente, verifico si$n
es primo contando cuántos números entre 2 y sí mismo lo dividen sin residuo (esa es lagrep...<2
parte), 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.fuente
$a%4>2
lugar de hacerlo$a%4==3
.golflua
147141El 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.
Devuelve 1 si es verdadero y 0 si no.
Una versión de Lua sin golf,
fuente
tonumber(io.read())
como argumento alg
final, y 2 más eliminando las nuevas líneasa
donde|a| <= |z|
ifa | z
(ifa
dividez
).APL (NARS), 99 caracteres, 198 bytes
prueba:
fuente
Encantamientos rúnicos , 41 bytes
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:
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).
fuente
Mathematica, 149 Personajes
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:
Bonus plot de todos los Primes Gaussianos de -20 a 20:
fuente
Rubí
-rprime
,656080 bytesNo noté la regla "no se puede usar isPrime" ...
Pruébalo en línea!
fuente
Python -
117 122121fuente
==3
con>2