Esta es mi primera pregunta de código de golf, y una muy simple, así que me disculpo de antemano si es posible que haya roto las pautas de la comunidad.
La tarea es imprimir, en orden ascendente, todos los números primos de menos de un millón. El formato de salida debe ser un número por línea de salida.
El objetivo, como con la mayoría de los envíos de códigos de golf, es minimizar el tamaño del código. La optimización para el tiempo de ejecución también es una ventaja, pero es un objetivo secundario.
code-golf
kolmogorov-complexity
primes
Delan Azabani
fuente
fuente
10^6
es aún más corto;)1e6
:-DRespuestas:
Mathematica ,
1724Solo para comparar:
Como se señaló en un comentario, no pude proporcionar una prima por línea; corrección:
fuente
Prime~Array~78498
también 17 :)Print/@
y terminar con;
para evitar la salida de una larga lista deNull
soluciones que, al costo de 8 caracteres adicionales.Python 3, 46 bytes
Para cuando el ciclo llega a la prueba
k
, ha calculado iterativamente el factorial cuadradoP=(k-1)!^2
. Sik
es primo, entonces no aparece en el producto1 * 2 * ... * (k-1)
, por lo que no es un factor deP
. Pero, si es compuesto, todos sus factores primos son más pequeños y, por lo tanto, en el producto. La cuadratura solo es necesaria para evitark=4
falsamente ser llamada primo.Más fuertemente, del teorema de Wilson se deduce que cuando
k
es primo,P%k
es igual1
. Aunque solo necesitamos que no sea cero aquí, es útil en general queP%k
sea una variable indicadora de sik
es primo.fuente
C, 61 caracteres
Casi exactamente lo mismo que este (la pregunta es casi exactamente la misma también).
fuente
SEG-FAULT
después de imprimir881
-O3
agcc
resuelto el problema !!n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
MATLAB
(16)(12)Desafortunadamente, esto sale en una sola línea:
pero eso se resuelve mediante una simple transposición matricial:
y puedo recortar algunos caracteres usando notación exponencial (como se sugiere en los comentarios):
fuente
1e6
lugar de1000000
ayuda aquí también.'
finalBash (37 caracteres)
(60 caracteres)
en mi computadora (CPU de 2.0 GHz, 2 GB de RAM) toma 14 segundos.
fuente
seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
seq 1e6|factor|awk '$0=$2*!$3'
Es un poco más corto.c p
donde c es un enlace simbólico a cat y p es un archivo de texto con números primos de hasta un millón ... ¿puede hacerlo con shell incorporado?seq
yfactor
están adentrocoreutils
, así que es legítimo.sed
También es bastante ubicuo.coreutils
Puede ser tratado como un incorporado. Bash sin coreutils es como C ++ sin STL.J, 21 caracteres
que se puede acortar a
si sabe cuántos primos hay por debajo de 1000000.
fuente
,.
, en lugar de 1 [\\ para guardar un personaje. Retire el paréntesis innecesarios, y el uso de la notación exponencial:1e6
.,.i.&.(p:^:_1)1e6
no más corto (después de aplicar las sugerencias de @Omar) pero encontré interesante el uso de under.PowerShell,
4744 bytesMuy lento, pero lo más corto que se me ocurrió.
PowerShell, 123 bytes
Esto es mucho más rápido; lejos de ser óptimo, pero es un buen compromiso entre eficiencia y brevedad.
fuente
Rubí 34
fuente
Bash, 30 bytes
Como saeedn no actuará según mi sugerencia, que es más corta y más rápida que su enfoque, pensé en publicar mi propia respuesta:
Cómo funciona
enumera todos los enteros positivos hasta 1,000,000.
los factoriza uno por uno. Para los primeros diez, el resultado es el siguiente:
Finalmente,
cambia la línea completa (
$0
) al producto del segundo campo (el primer factor primo) y la negación lógica del tercer campo (1
si es un factor primo o menos, de lo0
contrario).Esto reemplaza las líneas correspondientes a los números primos con el número mismo y todas las demás líneas con ceros. Como awk solo imprime valores verdaderos, solo se imprimirá el número primo.
fuente
awk '$0=$2*!$3'
es genial!Ruby
5041fuente
.to_a
, ya que Enumerable ya lo incluyeselect
. También puede usar la notación abreviada para Symbol # to_proc para acortarlo aún más:p (2..1e6).select &:prime?
(1 no es primo)require'prime';p Prime.take 78498
.Bash, 37
Jugaré más al golf, si puedo ...
La mayor parte de esto está tratando de analizar
factor
el formato de salida incómodo.Tarda 5.7 segundos más o menos en completarse en mi máquina.
(Simplemente sucedió que mi publicación fue la primera en ir a la segunda página de respuestas, por lo que nadie la verá ...)
Vieja solución
Esto es más largo y más lento (toma 10 segundos).
fuente
factor
antes, ¡pero ahí está justo en coreutils!seq 1e6|factor|grep -oP "(?<=: )\d+$"
con una mirada perl-grep detrás-P
habilita expresiones regulares de estilo perl.(?<=: )
es una mirada positiva hacia atrás para la cadena ":". Básicamente, esto dice que ":" debe aparecer antes de lo que coincide\d+$
, pero en realidad no es parte de la coincidencia, por lo que la-o
opción solo nos da un número coincidente después de los dos puntos, es decir, solo da números donde solo hay un factor, es decir, primo.Python 3.x: 66 caracteres
Solución más eficiente: 87 caracteres
Basado en el tamiz de Eratóstenes.
fuente
0
y1
. Puede solucionar esto usando en su lugarrange(2,10**6)
. Además, creo que laif
declaración debe estar en una línea separada de la salidafor
o obtendrá un error.Haskell, 51
fuente
mapM_
amapM
, el valor de retorno no se imprimirá, y este es Code Golf. ;)APL, 15
Mi intérprete se topó con problemas de memoria, pero funciona en teoría.
fuente
⍪
frente para hacer un número por línea, y no necesita el,
.⍳
son los primeros enteros.1↓
deja caer el primero.p←
asigna a la p.p∘.×p
hace una tabla de multiplicarp~
elimina de p lo que esté a la derecha. (,
no es necesario, divide la tabla en una lista).Perl, 49 bytes
Expresión regular kung fu :)
Versión sin golf:
¡Ni siquiera ha progresado un 10% mientras escribo esta publicación!
Fuente para la expresión regular: http://montreal.pm.org/tech/neil_kandalgaonkar.shtml
fuente
1000000
se puede escribir10**6
Julia, 11
Parece que los complementos incorporados están recibiendo votos positivos, además, necesitaba más palabras para una respuesta más larga.
fuente
J (15 o 9)
No puedo creer que esto venza a Mathematica (incluso si es solo
unopor 2 caracteres)O:
fuente
... The output format should be one number per line of output.
Por eso mi respuesta comienza con1[\
.gs2, 5 bytes
Codificado en CP437:
1C 29
empuja un millón,11 6C
es primos a continuación,54
es mostrar líneas.fuente
GolfScript, 22/20 (20/19) bytes
A costa de la velocidad, el código puede hacerse dos bytes más corto:
Si no se tiene en cuenta el formato de salida especificado en la pregunta editada (que es lo que hacen muchas de las respuestas existentes), se pueden guardar dos bytes en la versión rápida y uno en la lenta:
Esto imprimirá un LF adicional después de los números primos para la versión rápida, e imprimirá los números primos como una matriz para la versión lenta.
Cómo funciona
Ambas versiones son implementaciones del tamiz de Eratóstenes .
La versión rápida hace lo siguiente:
Establecer
A = [ 2 3 4 … 999,999 ]
y| = [ 0 1 2 … 999,999 ]
.Establecer
N = A[0]
e imprimirN
.Recoge todos los elementos N-ésimo de
|
adentroC
. Estos son los múltiplos deN
.Conjunto
A = A - C
.Si
A
no está vacío, regrese a 2.La versión lenta funciona de manera similar, pero en lugar de eliminar sucesivamente múltiplos del mínimo de "A" (que siempre es primo), elimina los múltiplos de todos los enteros positivos por debajo de 1,000,000.
Competitividad
En ausencia de funciones matemáticas integradas para factorizar o verificar la primalidad, todas las soluciones de GolfScript serán muy grandes o muy ineficientes.
Si bien aún estoy lejos de ser eficiente, creo que he logrado una relación de velocidad a tamaño decente. En el momento de su presentación, este enfoque parece ser el más corto de los que no utilizan ninguno de los elementos incorporados anteriormente mencionados. Digo parece porque no tengo idea de cómo funcionan algunas de las respuestas ...
He comparado las cuatro soluciones de GolfScript presentadas: w0lf (división de prueba), mi otra respuesta (teorema de Wilson) y las dos de esta respuesta. Estos fueron los resultados:
fuente
NARS2000 APL, 7 caracteres
fuente
Golfscript
26 2524Editar (ahorró un personaje más gracias a Peter Taylor):
Código antiguo
Este código solo tiene un valor teórico, ya que es increíblemente lento e ineficiente. Creo que podría llevar horas correr.
Si desea probarlo, intente, por ejemplo, solo los primos de hasta 100:
fuente
\;
con*
. (También puede ser mucho más rápido para el conteo de personajes actual al encontrar el primer divisor en lugar de todos ellos:10 6?,2>{.),2>{1$\%!}?=},`
.,
con:x,
y\.@
conx\
(el espacio en blanco se debe a problemas de escape con MD en los comentarios) y eliminar*
.CJam - 11
1e6,
- matriz de 0 ... 999999{mp},
- seleccionar primosN*
- unirse con nuevas líneasfuente
GolfScript, 25 (24) bytes
Si no se tiene en cuenta el formato de salida especificado en la pregunta editada, se puede guardar un byte:
Esto imprimirá los primos como una matriz (como lo hacen muchas otras soluciones) en lugar de una por línea.
Cómo funciona
La idea general es usar el teorema de Wilson , que establece que n > 1 es primo si y solo si
Puntos de referencia
Más rápido que la división de prueba, pero más lento que el tamiz de Eratóstenes. Ver mi otra respuesta .
fuente
Java, 110 bytes
Usar la división unaria a través de la expresión regular como prueba de primalidad.
fuente
C,
9188858281807672 caracteresEl algoritmo es terriblemente ineficiente, pero como estamos haciendo golf de código eso no debería importar.
fuente
main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}
o alguna idea como esta (ya que en realidad no loi
seguro ser 0? Creo que, si proporciona algún argumento, fallará. Además, creo quej
tendrá algún tipo de error de tipo.b
Aunque no estoy seguro .Mathematica 25
Suponiendo que no conoce el número de primos menores que 10 ^ 6:
fuente
J, 16 caracteres
Sin el requisito de formato de salida, esto se puede reducir a 13 caracteres:
1]\
simplemente toma la matriz de números primos de rango 1, la convierte en una matriz de rango 2 y coloca cada primo en su propia fila, por lo que el formato de salida predeterminado del intérprete convierte la lista de una línea en una prima por línea.(#~ f) y
es básicamentefilter
, dondef
devuelve un booleano para cada elemento eny
.i.1e6
es el rango de enteros [0,1000000), y1&p:
es una función booleana que devuelve 1 para primos.fuente
R,
4543 caracteresPara cada número x de 2 a 1e6, simplemente imprímalo si el número de x mod 2 a x que es igual a 0 es menor que 2.
fuente
Golpe (433643)
Mi intento (no tan inteligente) fue usar factor para factorizar el producto.
Desafortunadamente, con grandes números, el producto es, por supuesto, enorme. También tardó más de 12 horas en ejecutarse. Sin embargo, decidí publicarlo porque pensé que era único.
Aquí está el código completo.
Si fuera primos menores de seis años sería razonable.
Oh bueno, lo intenté.
fuente
factor
mucho peor que el algoritmo básico de división de prueba.C #, 70
No vas a ver mucho aquí durante mucho tiempo ...
fuente
double
1e6
a anint
, peroint
es requerido porRange
. (2) Lo internoRange
debe tomar en la mayoría de losn-2
términos, de lo contrario, probarán % n
cuál es claramente0
. (3) Escribesx%n
cuando quieresn%x
. Al solucionar estos problemas, algo como esto funcionará: sinEnumerable.Range(2,999999).Where(n=>Enumerable.Range(2,n-2).All(x=>n%x!=0))
embargo, esto todavía no genera los números; El requisito era uno por línea.