Lista de primos por debajo de un millón

56

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.

Delan Azabani
fuente
12
No es un duplicado exacto, pero es esencialmente la prueba de primalidad simplemente, que es un componente de una serie de preguntas existentes (por ejemplo codegolf.stackexchange.com/questions/113 , codegolf.stackexchange.com/questions/5087 , codegolf.stackexchange. com / preguntas / 1977 ). FWIW, una directriz que no se sigue lo suficiente (incluso por personas que deberían saberlo mejor) es pre-proponer una pregunta en el meta sandbox meta.codegolf.stackexchange.com/questions/423 para criticar y discutir cómo puede ser mejorado antes de que la gente empiece a responderlo.
Peter Taylor
Ah, sí, me preocupaba que esta pregunta fuera demasiado similar a la gran cantidad de preguntas relacionadas con números primos que ya existen.
Delan Azabani
2
@ GlennRanders-Pehrson Porque 10^6es aún más corto;)
ɐɔıʇǝɥʇuʎs
1
Hace unos años, presenté una entrada de IOCCC que imprime primos con solo 68 caracteres en C; desafortunadamente, se detiene mucho menos que un millón, pero puede ser de interés para algunos: computronium.org/ioccc.html
Computronium
1
@ ɐɔıʇǝɥʇuʎs ¿Qué tal 1e6:-D
Titus

Respuestas:

33

Mathematica , 17 24

Solo para comparar:

Prime@Range@78498

Como se señaló en un comentario, no pude proporcionar una prima por línea; corrección:

Column@Prime@Range@78498
Señor mago
fuente
44
Prime~Array~78498también 17 :)
chyanog
Serían nueve bytes en mthmca, si eso fuera a ser lanzado.
Michael Stern
Eso viola la condición de una prima por línea de salida. Prefijar con Print/@y terminar con ;para evitar la salida de una larga lista de Nullsoluciones que, al costo de 8 caracteres adicionales.
celtschk
@celtschk No sé si me perdí o descuidé eso hace cinco años.
Mr.Wizard
1
Bueno, definitivamente extrañé que fuera de hace cinco años :-)
celtschk
27

Python 3, 46 bytes

k=P=1
while k<1e6:P%k and print(k);P*=k*k;k+=1

Para cuando el ciclo llega a la prueba k, ha calculado iterativamente el factorial cuadrado P=(k-1)!^2. Si kes primo, entonces no aparece en el producto 1 * 2 * ... * (k-1), por lo que no es un factor de P. 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 evitar k=4falsamente ser llamada primo.

Más fuertemente, del teorema de Wilson se deduce que cuando kes primo, P%kes igual 1. Aunque solo necesitamos que no sea cero aquí, es útil en general que P%ksea ​​una variable indicadora de si kes primo.

xnor
fuente
23

C, 61 caracteres

Casi exactamente lo mismo que este (la pregunta es casi exactamente la misma también).

n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}
Ugoren
fuente
Conseguido SEG-FAULTdespués de imprimir881
manav mn
77
@Manav, quizás compiló sin optimizaciones. Se basa en un buen optimizador, que eliminará la recurrencia.
ugoren
44
Sí, añadiendo -O3a gccresuelto el problema !!
manav mn
Este método es una locura. Me encanta.
Todd Lehman
2
Puedo llevarte a 57 bytesn=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
Albert Renshaw
22

MATLAB (16) (12)

Desafortunadamente, esto sale en una sola línea:

primes(1000000)

pero eso se resuelve mediante una simple transposición matricial:

primes(1000000)'

y puedo recortar algunos caracteres usando notación exponencial (como se sugiere en los comentarios):

primes(1e6)'
MBraedley
fuente
55
Usar en 1e6lugar de 1000000ayuda aquí también.
orion
@orion Eso tendría 11 caracteres
Axoren
@Axoren que no incluye el 'final
Stan Strum
20

Bash (37 caracteres)

seq 2 1e6|factor|sed 's/.*: //g;/ /d'

(60 caracteres)

seq 2 1000000|factor|sed -e 's/[0-9]*: //g' -e '/^.* .*$/ d'

en mi computadora (CPU de 2.0 GHz, 2 GB de RAM) toma 14 segundos.

saeedn
fuente
Esto se puede mejorar para: seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
Delan Azabani
sí tienes razón. Escribí mi comando sed limpio, no golf: P
saeedn
3
seq 1e6|factor|awk '$0=$2*!$3'Es un poco más corto.
Dennis
1
seq, factor y sed son programas externos, esto también podría ser c pdonde 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?
technosaurus
77
@technosaurus seqy factorestán adentro coreutils, así que es legítimo. sedTambién es bastante ubicuo. coreutilsPuede ser tratado como un incorporado. Bash sin coreutils es como C ++ sin STL.
16

J, 21 caracteres

1[\p:i.(_1 p:1000000)

que se puede acortar a

1[\p:i.78498

si sabe cuántos primos hay por debajo de 1000000.

Gareth
fuente
2
Usando elementos enfile ,., en lugar de 1 [\\ para guardar un personaje. Retire el paréntesis innecesarios, y el uso de la notación exponencial: 1e6.
Omar
Se me ocurrió esto: ,.i.&.(p:^:_1)1e6no más corto (después de aplicar las sugerencias de @Omar) pero encontré interesante el uso de under.
kaoD
10

PowerShell, 47 44 bytes

Muy lento, pero lo más corto que se me ocurrió.

$p=2..1e6;$p|?{$n=$_;!($p-lt$_|?{!($n%$_)})}

PowerShell, 123 bytes

Esto es mucho más rápido; lejos de ser óptimo, pero es un buen compromiso entre eficiencia y brevedad.

 $p=2..1e6;$n=0
 while(1){$p=@($p[0..$n]|?{$_})+($p[($n+1)..($p.count-1)]|?{$_%$p[$n]});$n++;if($n-ge($p.count-1)){break}}
 $p
Rynant
fuente
9

Rubí 34

require'prime';p Prime.take 78498
Hauleth
fuente
9

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:

seq 1e6|factor|awk '$0=$2*!$3'

Cómo funciona

seq 1e6

enumera todos los enteros positivos hasta 1,000,000.

factor

los factoriza uno por uno. Para los primeros diez, el resultado es el siguiente:

1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5

Finalmente,

awk '$0=$2*!$3'

cambia la línea completa ( $0) al producto del segundo campo (el primer factor primo) y la negación lógica del tercer campo ( 1si es un factor primo o menos, de lo 0contrario).

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.

Dennis
fuente
44
awk '$0=$2*!$3'es genial!
yeti
8

Ruby 50 41

require'mathn'
p (2..1e6).select &:prime?
Cristian Lupascu
fuente
2
No es necesario .to_a, ya que Enumerable ya lo incluye select. 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)
Ventero
@Ventero muchas gracias! No sabía sobre el símbolo # to_proc. Tengo que prestar más atención a los atajos que ofrece Ruby.
Cristian Lupascu
2
Versión mas corta require'prime';p Prime.take 78498.
Hauleth
@ ŁukaszNiemier ¡Genial! Creo que es tan diferente que puedes publicarlo como una respuesta separada.
Cristian Lupascu el
Buen uso de algunos buenos 'country boy mathn'
DoctorHeckle
8

Bash, 37

Jugaré más al golf, si puedo ...

La mayor parte de esto está tratando de analizar factorel formato de salida incómodo.

seq 1e6|factor|grep -oP "(?<=: )\d+$"

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

seq 1e6|factor|egrep ':.\S+$'|grep -oE '\S+$'

fuente
2
Wow, nunca me había encontrado factorantes, ¡pero ahí está justo en coreutils!
Trauma digital
1
Afeitarse un personaje: seq 1e6|factor|grep -oP "(?<=: )\d+$"con una mirada perl-grep detrás
Digital Trauma
@DigitalTrauma cómo funciona eso
1
-Phabilita 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 -oopció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.
Trauma digital
@DigitalTrauma agregado
8

Python 3.x: 66 caracteres

for k in range(2,10**6):
 if all(k%f for f in range(2,k)):print(k)

Solución más eficiente: 87 caracteres

Basado en el tamiz de Eratóstenes.

p=[];z=range(2,10**6)
while z:f=z[0];p+=[f];z=[k for k in z if k%f]
for k in p:print(k)
dan04
fuente
1
El primero imprime erróneamente 0y 1. Puede solucionar esto usando en su lugar range(2,10**6). Además, creo que la ifdeclaración debe estar en una línea separada de la salida foro obtendrá un error.
xnor
@xnor: lo arregló.
dan04
8

Haskell, 51

mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]
pt2121
fuente
Puede cambiar mapM_a mapM, el valor de retorno no se imprimirá, y este es Code Golf. ;)
Dogbert el
¿Por qué hay espacios adicionales después de imprimir y en (> 0)?
orgulloso Haskeller
¡buena atrapada! gracias
pt2121
Puede reemplazar 999999 con 10 ^ 6. Y actualice su recuento de bytes: 63 no puede ser correcto.
user2845840
@ user2845840 ok gracias. ¡buena idea!
pt2121
8

APL, 15

p~,p∘.×p←1↓⍳1e6

Mi intérprete se topó con problemas de memoria, pero funciona en teoría.

TwiNight
fuente
¿Cómo? ¿Puedes darme una nota?
Rasmus Damgaard Nielsen
Necesita un frente para hacer un número por línea, y no necesita el ,.
Adám
@RasmusDamgaardNielsen son los primeros enteros. 1↓deja caer el primero. p←asigna a la p. p∘.×phace una tabla de multiplicar p~elimina de p lo que esté a la derecha. ( ,no es necesario, divide la tabla en una lista).
Adám
8

Perl, 49 bytes

Expresión regular kung fu :)

for(1..1E6){(1x$_)=~/^(11+?)\1+$/ or print"$_\n"}

Versión sin golf:

for(1 .. 1_000_000) { 
    (1x$_) =~ /^(11+?)\1+$/ or print "$_\n";
}

¡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

Gowtham
fuente
2
me inspiró a escribir una versión perl6. también, 1000000se puede escribir10**6
pabo
1
Además, 1000000 se puede escribir 1E6
mob
Actualicé mi respuesta. Gracias @mob
Gowtham
Siempre fue una de mis expresiones favoritas, pero debes recordar que falla espectacularmente una vez que alcanzas números más altos, debido al hecho de que está convirtiendo números enormes en unarios. Es posible que esta expresión regular no funcione para encontrar números primos en los cientos de miles y más, dependiendo de la configuración del idioma (y su máquina)
Codefun64
7

Julia, 11

primes(10^6)

Parece que los complementos incorporados están recibiendo votos positivos, además, necesitaba más palabras para una respuesta más larga.

gggg
fuente
7

J (15 o 9)

No puedo creer que esto venza a Mathematica (incluso si es solo uno por 2 caracteres)

a#~1 p:a=:i.1e6

O:

p:i.78498
ɐɔıʇǝɥʇuʎs
fuente
1
... The output format should be one number per line of output.Por eso mi respuesta comienza con 1[\ .
Gareth
6

gs2, 5 bytes

Codificado en CP437:

∟)◄lT

1C 29empuja un millón, 11 6Ces primos a continuación, 54es mostrar líneas.

Lynn
fuente
5

GolfScript, 22/20 (20/19) bytes

n(6?,:|2>{(.p|%-.}do:n

A costa de la velocidad, el código puede hacerse dos bytes más corto:

n(6?,:|2>.{|%2>-}/n*

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:

n(6?,:|2>{(.p|%-.}do
n(6?,:|2>.{|%2>-}/`

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:

  1. Establecer A = [ 2 3 4 … 999,999 ]y | = [ 0 1 2 … 999,999 ].

  2. Establecer N = A[0]e imprimir N.

  3. Recoge todos los elementos N-ésimo de |adentro C. Estos son los múltiplos de N.

  4. Conjunto A = A - C.

  5. Si Ano está vacío, regrese a 2.

n(6?   # Push "\n".pop() ** 6 = 1,000,000.
,:|    # Push | = [ 0 1 2 … 999,999 ].
,2>    # Push A = [ 2 3 4 … 999,999 ].
{      #
  (    # Unshift the first element (“N”) of “A”.
  .p   # Print “N”.
  |%   # Collect every N-th element from “A” into a new array, starting with the first.
  -    # Take the set difference of “A” and the array from above.
  .    # Duplicate the set difference.
}do    # If the set difference is non-empty, repeat.
:n     # Store the empty string in “n”, so no final LF will get printed.

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:

Bound     | Trial division     | Sieve (slow)       | Wilson's theorem | Sieve (fast)
----------+--------------------+--------------------+------------------+----------------
1,000     | 2.47 s             | 0.06 s             | 0.03 s           | 0.03 s
10,000    | 246.06 s (4.1 m)   | 1.49 s             | 0.38 s           | 0.14 s
20,000    | 1006.83 s (16.8 m) | 5.22 s             | 1.41 s           | 0.38 s
100,000   | ~ 7 h (estimated)  | 104.65 (1.7 m)     | 35.20 s          | 5.82 s
1,000,000 | ~ 29 d (estimated) | 111136.97s (3.1 h) | 3695.92 s (1 h)  | 418.24 s (7 m)
Dennis
fuente
¿El tamiz "lento" es solo un tamiz de Eratóstenes?
dorukayhan
Ambos son. La versión lenta es solo una implementación horrible.
Dennis
5

NARS2000 APL, 7 caracteres

⍸0π⍳1e6
La colmena
fuente
3
¡Bienvenido a Programming Puzzles & Code Golf!
Dennis
4

Golfscript 26 25 24

Editar (ahorró un personaje más gracias a Peter Taylor):

10 6?,{:x,{)x\%!},,2=},`

Código antiguo

10 6?,{.,{)\.@%!},,2=*},`

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:

10 2?,{:x,{)x\%!},,2=},`
Cristian Lupascu
fuente
Puedes guardar un personaje reemplazándolo \;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$\%!}?=},`
Peter Taylor
@ PeterTaylor Gracias, usando la multiplicación hay un truco muy bueno.
Cristian Lupascu
Hay otro ahorro de caracteres con una variable: reemplazar .,con :x,y \.@con x\ (el espacio en blanco se debe a problemas de escape con MD en los comentarios) y eliminar *.
Peter Taylor
@PeterTaylor bueno, gracias! He editado mi código.
Cristian Lupascu 01 de
4

CJam - 11

1e6,{mp},N*

1e6,- matriz de 0 ... 999999
{mp},- seleccionar primos
N*- unirse con nuevas líneas

aditsu
fuente
1
¿No es CJam más reciente que esta pregunta?
Peter Taylor
@PeterTaylor oh, sí, lo es
aditsu
4

GolfScript, 25 (24) bytes

!10 6?,2>{.(@*.)@%!},n*\;

Si no se tiene en cuenta el formato de salida especificado en la pregunta editada, se puede guardar un byte:

!10 6?,2>{.(@*.)@%!},`\;

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

                                                      (n - 1)!  = -1 (mod n)

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

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 .

Dennis
fuente
3

C, 91 88 85 82 81 80 76 72 caracteres

main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}

El algoritmo es terriblemente ineficiente, pero como estamos haciendo golf de código eso no debería importar.

Gareth
fuente
1
puedes acortarlo fácilmente: 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 lo
compilé
¿Cómo es iseguro ser 0? Creo que, si proporciona algún argumento, fallará. Además, creo que jtendrá algún tipo de error de tipo. bAunque no estoy seguro .
Erik the Outgolfer
3

Mathematica 25

Suponiendo que no conoce el número de primos menores que 10 ^ 6:

Prime@Range@PrimePi[10^6]
DavidC
fuente
3

J, 16 caracteres

1]\(#~1&p:)i.1e6

Sin el requisito de formato de salida, esto se puede reducir a 13 caracteres:

(#~1&p:)i.1e6

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) yes básicamente filter, donde fdevuelve un booleano para cada elemento en y. i.1e6es el rango de enteros [0,1000000), y 1&p:es una función booleana que devuelve 1 para primos.

racionalis
fuente
3

R, 45 43 caracteres

for(i in 2:1e6)if(sum(!i%%2:i)<2)cat(i," ")

Para 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.

plannapus
fuente
El primer número producido por este código es 1, pero 1 no es primo.
Sven Hohenstein
@SvenHohenstein Gracias, corregido.
plannapus
3

Golpe (433643)

Mi intento (no tan inteligente) fue usar factor para factorizar el producto.

factor ${PRODUCT}

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.

  factor 30

Oh bueno, lo intenté.

Kevin Cox
fuente
+1 Esta respuesta es verdaderamente diabólica. No es un resultado calculado previamente (ahorra un poco de caracteres) y es mucho más terrible de calcular :) Posiblemente también sea un ejemplo que hace que el rendimiento optimizado sea factormucho peor que el algoritmo básico de división de prueba.
Orion
3

C #, 70

Enumerable.Range(1,1e6).Where(n=>Enumerable.Range(2,n).All(x=>x%n!=0))

No vas a ver mucho aquí durante mucho tiempo ...

Es notalie.
fuente
Hay varias razones por las cuales esto está mal. (1) No puede convertir implícitamente de a double 1e6a an int, pero intes requerido por Range. (2) Lo interno Rangedebe tomar en la mayoría de los n-2términos, de lo contrario, probará n % ncuál es claramente 0. (3) Escribes x%ncuando quieres n%x. Al solucionar estos problemas, algo como esto funcionará: sin Enumerable.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.
Jeppe Stig Nielsen