Las reglas son simples:

• Primero n primos (no primos debajo de n ), deben imprimirse en salida estándar separados por nuevas líneas (los primos deben generarse dentro del código)
• los primos no pueden ser generados por una función incorporada o a través de una biblioteca , es decir, el uso de una función incorporada o de una biblioteca como, por ejemplo, prime = get_nth_prime (n), is_a_prime (número) o factorlist = list_all_factors (número) no será muy creativo.

• Puntuación: Digamos que definimos Puntuación = f ([número de caracteres en el código]), siendo O ( f (n)) la complejidad de su algoritmo donde n es el número de números primos que encuentra. Entonces, por ejemplo, si tiene un código de 300 caracteres con complejidad O (n ^ 2), la puntuación es 300 ^ 2 = 90000 , para 300 caracteres con O (n * ln (n)), la puntuación se convierte en 300 * 5.7 = 1711.13 ( supongamos que todos los registros son registros naturales por simplicidad)

• Use cualquier lenguaje de programación existente, gana la puntuación más baja

Editar: El problema ha cambiado de encontrar 'primeros 1000000 primos' a 'primeros n primos' debido a una confusión sobre qué es 'n' en O (f (n)), n es el número de primos que encuentra (encontrar primos es el problema aquí y la complejidad del problema depende del número de primos encontrados)

Nota: para aclarar algunas confusiones sobre la complejidad, si 'n' es el número de primos que encuentra y 'N' es el enésimo primer encontrado, la complejidad en términos de n es y N no son equivalentes, es decir, O (f (n)). = O (f (N)) como, f (N)! = Constante * f (n) y N! = Constante * n, porque sabemos que la enésima función principal no es lineal, aunque ya que estábamos encontrando 'n' la complejidad de los números primos debe ser fácilmente expresable en términos de 'n'.

Como señaló Kibbee, puede visitar este sitio para verificar sus soluciones ( aquí está la antigua lista de documentos de Google)

Incluya estos en su solución -

• qué complejidad tiene su programa (incluya análisis básico si no es trivial)

• longitud de caracteres del código

• la puntuación final calculada

Esta es mi primera pregunta de CodeGolf, por lo tanto, si hay un error o una laguna en las reglas anteriores, indíquelas.

Python (129 caracteres, O (n * log log n), puntaje de 203.948)

Yo diría que el Tamiz de Eratóstenes es el camino a seguir. Muy simple y relativamente rápido.

N=15485864
a=[1]*N
x=xrange
for i in x(2,3936):
 if a[i]:
  for j in x(i*i,N,i):a[j]=0
print [i for i in x(len(a))if a[i]==1][2:]

Código mejorado de antes.

Python ( 191 156 152 caracteres, O (n * log log n) (?), Puntaje de 252.620 (?))

No puedo calcular la complejidad, esta es la mejor aproximación que puedo dar.

from math import log as l
n=input()
N=n*int(l(n)+l(l(n)))
a=range(2,N)
for i in range(int(n**.5)+1):
 a=filter(lambda x:x%a[i] or x==a[i],a)
print a[:n]

n*int(l(n)+l(l(n)))es el límite superior del nnúmero primo th.

Haskell, n ^ 1.1 tasa de crecimiento empírico, 89 caracteres, puntaje 139 (?)

Lo siguiente funciona en el indicador de GHCi cuando la biblioteca general que usa se ha cargado previamente. Imprimir n -ésimo primer, basado en 1

let s=3:minus[5,7..](unionAll[[p*p,p*p+2*p..]|p<-s])in getLine>>=(print.((0:2:s)!!).read)

Este es un tamiz ilimitado de Eratóstenes, que usa una biblioteca de uso general para listas ordenadas. Complejidad empírica entre 100,000 y 200,000 primos O(n^1.1). Se adapta a O(n*log(n)*log(log n)).

Sobre la estimación de la complejidad

Medí tiempo de ejecución para 100k y 200k números primos, entonces calculados logBase 2 (t2/t1), que produjeron n^1.09. Definir g n = n*log n*log(log n), calcular logBase 2 (g 200000 / g 100000)da n^1.12.

Entonces 89**1.1 = 139, aunque g(89) = 600. --- (?)

Parece que para calificar la tasa de crecimiento estimada debería usarse en lugar de la función de complejidad en sí misma. Por ejemplo, g2 n = n*((log n)**2)*log(log n)es mucho mejor que n**1.5, pero para 100 caracteres los dos producen puntaje de 3239y 1000, respectivamente. Esto no puede estar bien. La estimación en un rango de 200k / 100k da logBase 2 (g2 200000 / g2 100000) = 1.2y, por lo tanto, una puntuación de 100**1.2 = 251.

Además, yo no trato de imprimir todos los números primos, sólo el n primer lugar -ésimo.

Sin importaciones, 240 caracteres. n ^ 1.15 tasa de crecimiento empírico, puntaje 546.

main=getLine>>=(print.s.read)
s n=let s=3:g 5(a[[p*p,p*p+2*p..]|p<-s])in(0:2:s)!!n
a((x:s):t)=x:u s(a$p t)
p((x:s):r:t)=(x:u s r):p t
g k s@(x:t)|k<x=k:g(k+2)s|True=g(k+2)t
u a@(x:r)b@(y:t)=case(compare x y)of LT->x:u r b;EQ->x:u r t;GT->y:u a t

Haskell, 72 89 caracteres, O (n ^ 2), Puntuación 7921

La puntuación más alta por recuento de char gana. Modificado para el primer N. Además, aparentemente no puedo usar una calculadora, por lo que mi puntaje no es tan abismalmente malo como pensaba. (usando la complejidad para la división de prueba básica como se encuentra en la fuente a continuación).

Según Will Ness, el siguiente no es un programa completo de Haskell (en realidad se basa en REPL). El siguiente es un programa más completo con un pseudo tamiz (las importaciones realmente ahorran un carbón, pero no me gustan las importaciones en el código de golf).

main=getLine>>= \x->print.take(read x).(let s(x:y)=x:s(filter((>0).(`mod`x))y)in s)$[2..]

Esta versión es sin duda (n ^ 2). El algoritmo es solo una versión de golf del ingenuo `` tamiz '', como se ve aquí Old ghci 1 liner

getLine>>= \x->print.take(read x)$Data.List.nubBy(\x y->x`mod`y==0)[2..]

Dejando la vieja y engañosa respuesta porque la biblioteca a la que enlaza es bastante agradable.

print$take(10^6)Data.Numbers.Primes.primes

Vea aquí para una implementación y los enlaces para la complejidad del tiempo. Lamentablemente, las ruedas tienen un tiempo de búsqueda de registro (n), lo que nos ralentiza en un factor.

C #, 447 caracteres, bytes 452, puntaje?

using System;namespace PrimeNumbers{class C{static void GN(ulong n){ulong primes=0;for (ulong i=0;i<(n*3);i++){if(IP(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}static bool IP(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}static void Main(string[] args){ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GN(i);}}}}

Scriptcs Variante, 381 caracteres, 385 bytes, puntuación?

using System;static void GetN(ulong n){ulong primes=0;for (ulong i=0;i<(n*500);i++){if(IsPrime(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}public static bool IsPrime(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GetN(i);}

Si instala scriptcs, puede ejecutarlo.

PD: escribí esto en Vim :D

GolfScript (45 caracteres, puntuación reclamada ~ 7708)

~[]2{..3${1$\%!}?={.@\+\}{;}if)1$,3$<}do;\;n*

Esto hace una simple división de prueba por primos. Si está cerca del filo de Ruby (es decir, usando 1.9.3.0), la aritmética usa la multiplicación Toom-Cook 3, por lo que una división de prueba es O (n ^ 1.465) y el costo total de las divisiones es O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)†. Sin embargo, en GolfScript, agregar un elemento a una matriz requiere copiar la matriz. Lo he optimizado para copiar la lista de números primos solo cuando encuentra un nuevo número primo, así que solo nveces en total. Cada operación de copia es O(n)artículos de tamaño O(ln(n ln n)) = O(ln n)†, dando O(n^2 ln n).

Y esto, niños y niñas, es la razón por la cual GolfScript se usa para jugar golf en lugar de para una programación seria.

† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). Debería haberlo visto antes de comentar varias publicaciones ...

¡Esto es tan fácil que incluso mi editor de texto puede hacerlo!

Vim: 143 pulsaciones de teclas (115 acciones): O (n ^ 2 * log (n)): Puntuación: 101485.21

Sumisión:

qpqqdqA^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddmpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p

Entrada: N debe estar en la primera línea de un documento en blanco. Una vez finalizado esto, cada primo de 2 a N será una línea separada.

Ejecutando los comandos:

Primero, tenga en cuenta que cualquier comando con un cursor delante significa que debe mantener presionada la tecla Ctrl y escribir la siguiente letra (por ejemplo, ^ V es Ctrl-vy ^ R es Ctrl-r).

Esto sobrescribirá cualquier cosa en sus registros @a, @b, @d y @p.

Debido a que esto usa qcomandos, no se puede colocar en una macro. Sin embargo, aquí hay algunos consejos para ejecutarlo.

• qpqqdq solo borra registros
• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddcreará una lista de números 2 a N + 1. Este es un descanso entre las dos partes principales, por lo que una vez hecho esto, no debería necesitar hacerlo nuevamente.
• mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@pnecesita ser escrito de una vez. Trate de evitar el retroceso, ya que puede arruinar algo.
  • Si comete un error, escriba e qdqqpqintente esta línea nuevamente.

Para N grande, esto es muy lento. Le tomó alrededor de 27 minutos ejecutar N = 5000; considérate advertido.

Algoritmo:

Esto utiliza un algoritmo recursivo básico para encontrar primos. Dada una lista de todos los primos entre 1 y A, A + 1 es primo si no es divisible por ninguno de los números en la lista de primos. Comience en A = 2 y agregue números primos a la lista a medida que se encuentren. Después de N recursiones, la lista contendrá todos los números primos hasta N.

Complejidad

Este algoritmo tiene una complejidad de O (nN), donde N es el número de entrada yn es el número de números primos hasta N. Cada recursividad prueba n números y se realizan N recursiones, dando O (nN).

Sin embargo, N ~ n * log (n), dando la complejidad final como O (n ² * log (n)) ( https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number )

Explicación

No es fácil discernir el flujo del programa de los comandos vim, así que lo reescribí en Python siguiendo el mismo flujo. Al igual que el código Vim, el código de Python generará un error cuando llegue al final. Python no le gusta demasiada recursividad; si prueba este código con N> 150 más o menos, alcanzará la profundidad máxima de recursión

N = 20
primes = range(2, N+1)

# Python needs these defined.
mark_p = b = a = -1

# Check new number for factors. 
# This macro could be wrapped up in @d, but it saves space to leave it separate.
def p():
    global mark_d, mark_p, primes, a
    mark_d = 0
    print(primes)
    a = primes[mark_p]
    d()      

# Checks factor and determine what to do next
def d():
    global mark_d, mark_p, a, b, primes
    b = primes[mark_d]
    if(a == b): # Number is prime, check the next number
        mark_p += 1
        p()
    else:
        if(a%b == 0): # Number is not prime, delete it and check next number
            del(primes[mark_p])
            p()
        else: # Number might be prime, try next possible factor
            mark_d += 1
            d()

mark_p = 0 #Start at first number         
p()

Ahora, para desglosar las pulsaciones de teclas reales!

• qpqqdqBorra los registros @d y @p. Esto asegurará que nada se ejecute al configurar estas macros recursivas.

• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddConvierte la entrada en una lista de números del 2 al N + 1. La entrada N + 1 se elimina como un efecto secundario de la configuración de la macro @d.

  • Específicamente, escribe una macro que incrementa un número, luego la copia en la siguiente línea, luego escribe un 1 y ejecuta esta macro N veces.

• mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qescribe la macro @d, que implementa la función d () anterior. Las declaraciones "If" son interesantes de implementar en Vim. Mediante el uso del operador de búsqueda *, es posible elegir un determinado camino a seguir. Rompiendo el comando más abajo obtenemos

  • mpqdEstablezca la marca p aquí y comience a grabar la macro @d. La marca p debe establecerse para que haya un punto conocido al que saltar mientras se ejecuta
  • o^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc> Escribe el texto de la declaración if / else
  • 0*w*wyiWdd@0 en realidad ejecuta la instrucción if.
  • Antes de ejecutar este comando, la línea contendrá @a @b 0 0 `pj@p @a 0 (@a%@b) `pdd@p 0 `dj@d
  • 0 mueve el cursor al comienzo de la línea

  • *w*w Mueve el cursor al código para ejecutarlo a continuación

    1. if @a == @b, es decir `pj@p, que se mueve al siguiente número para @a y ejecuta @p en él.
    2. si @a! = @b y @ a% @ b == 0, es decir `pdd@p, que elimina el número actual @a, luego ejecuta @p en el siguiente.
    3. si @a! = @b y @ a %% b! = 0, es decir `dj@d, que comprueba el siguiente número para @b para ver si es un factor de @a

  • yiWdd@0 coloca el comando en el registro 0, elimina la línea y ejecuta el comando

  • q finaliza la grabación de la macro @d

• Cuando se ejecuta por primera vez, se ejecuta el `pdd@pcomando, eliminando la línea N + 1.

• qpmp"aywgg@dq escribe la macro @p, que guarda el número debajo del cursor, luego va a la primera entrada y ejecuta @d en eso.

• gg@p en realidad ejecuta @p para que se repita en todo el archivo.

QBASIC, 98 caracteres, Complejidad N Sqrt (N), Puntuación 970

I=1
A:I=I+2
FOR J=2 TO I^.5
    IF I MOD J=0 THEN GOTO A
NEXT
?I
K=K+1
IF K=1e6 THEN GOTO B
GOTO A
B:

Scala 263 caracteres

Actualizado para adaptarse a los nuevos requisitos. El 25% del código trata de encontrar un límite superior razonable para calcular los números primos a continuación.

object P extends App{
def c(M:Int)={
val p=collection.mutable.BitSet(M+1)
p(2)=true
(3 to M+1 by 2).map(p(_)=true)
for(i<-p){
var j=2*i;
while(j<M){
if(p(j))p(j)=false
j+=i}
}
p
}
val i=args(0).toInt
println(c(((math.log(i)*i*1.3)toInt)).take(i).mkString("\n"))
}

Tengo un tamiz también.

Aquí hay una prueba empírica de los costos de cálculo, sin necesidad de análisis:

object PrimesTo extends App{
    var cnt=0
    def c(M:Int)={
        val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
        for (i <- List.range (3, M, 2)
            if (p (i))) {
                var j=2*i;
                while (j < M) {
                    cnt+=1
                    if (p (j)) 
                        p(j)=false
                    j+=i}
            }
        (1 to M).filter (x => p (x))
    }
    val i = args(0).toInt
    /*
        To get the number x with i primes below, it is nearly ln(x)*x. For small numbers 
        we need a correction factor 1.13, and to avoid a bigger factor for very small 
        numbers we add 666 as an upper bound.
    */
    val x = (math.log(i)*i*1.13).toInt+666
    println (c(x).take (i).mkString("\n"))
    System.err.println (x + "\tcount: " + cnt)
}
for n in {1..5} ; do i=$((10**$n)); scala -J-Xmx768M P $i ; done 

conduce a los siguientes recuentos:

List (960, 1766, 15127, 217099, 2988966)

No estoy seguro de cómo calcular la puntuación. ¿Vale la pena escribir 5 caracteres más?

scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.13).toInt+666) 
res42: List[Int] = List(672, 756, 1638, 10545, 100045, 1000419, 10068909, 101346800, 1019549994)

scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.3)toInt) 
res43: List[Int] = List(7, 104, 1119, 11365, 114329, 1150158, 11582935, 116592898, 1172932855)

Para n mayor, reduce los cálculos en aproximadamente un 16% en ese rango, pero afaik para la fórmula de puntaje, ¿no consideramos factores constantes?

Nuevas consideraciones Big-O:

Para encontrar 1 000, 10 000, 100 000 primos, etc., utilizo una fórmula sobre la densidad de primos x => (math.log (x) * x * 1.3 que determina el bucle externo que estoy ejecutando.

Entonces, para los valores i en 1 a 6 => NPrimes (10 ^ i) ejecuta 9399, 133768 ... veces el bucle externo.

Encontré esta función O iterativamente con la ayuda del comentario de Peter Taylor, quien sugirió un valor mucho más alto para la exponenciación, en lugar de 1.01 sugirió 1.5:

def O(n:Int) = (math.pow((n * math.log (n)), 1.01)).toLong

O: (n: Int) Largo

val ns = List(10, 100, 1000, 10000, 100000, 1000*1000).map(x=>(math.log(x)*x*1.3)toInt).map(O) 

ns: List [Long] = List (102, 4152, 91532, 1612894, 25192460, 364664351)

 That's the list of upper values, to find primes below (since my algorithm has to know this value before it has to estimate it), send through the O-function, to find similar quotients for moving from 100 to 1000 to 10000 primes and so on: 

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
40.705882352941174
22.045279383429673
17.62109426211598
15.619414543051187
14.47513863274964
13.73425213148954

Estos son los cocientes, si uso 1.01 como exponente. Esto es lo que el contador encuentra empíricamente:

ns: Array[Int] = Array(1628, 2929, 23583, 321898, 4291625, 54289190, 660847317)

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
1.799140049140049
8.051553431205189
13.649578085909342
13.332251210010625
12.65003116535112
12.172723833234572

Los primeros dos valores son valores atípicos, porque he realizado una corrección constante para mi formulario de estimación para valores pequeños (hasta 1000).

Con la sugerencia de Peter Taylors de 1.5 se vería así:

245.2396265560166
98.8566987153728
70.8831374743478
59.26104390040363
52.92941829568069
48.956394784317816

Ahora con mi valor llego a:

O(263)
res85: Long = 1576

Pero no estoy seguro, qué tan cerca puedo llegar con mi función O a los valores observados.

Ruby 66 caracteres, O (n ^ 2) Puntuación - 4356

lazyestá disponible desde Ruby 2.0, y 1.0/0es un buen truco para obtener un rango infinito:

(2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j==0}}.take(n).to_a

Ruby, 84 caracteres, 84 bytes, puntuación?

Este es probablemente un poco demasiado novato para estas partes, pero me divertí mucho haciéndolo. Simplemente se repite hasta que f(primos encontrados) sea igual al nnúmero deseado de primos que se encontrarán.

La parte divertida es que para cada ciclo crea una matriz de 2 a uno menos que el número que se está inspeccionando. Luego, asigna cada elemento de la matriz para que sea el módulo del número original y el elemento, y verifica si alguno de los resultados es cero.

Además, no tengo idea de cómo calificarlo.

Actualizar

Código compactado e incluido un valor (totalmente arbitrario) para n

n,f,i=5**5,0,2
until f==n;f+=1;p i if !(2...i).to_a.map{|j|i%j}.include?(0);i+=1;end

Original

f, i = 0, 2
until f == n
  (f += 1; p i) if !(2...i).to_a.map{|j| i % j}.include?(0)
  i += 1
end

El i += 1bit y el untilbucle me saltan como áreas de mejora, pero en esta pista estoy un poco atascado. De todos modos, fue divertido pensar en eso.

Scala, 124 caracteres

object Q extends App{Stream.from(2).filter(p=>(2 to p)takeWhile(i=>i*i<=p)forall{p%_!= 0})take(args(0)toInt)foreach println}

División de prueba simple hasta la raíz cuadrada. La complejidad, por lo tanto, debe ser O (n ^ (1.5 + epsilon))

124 ^ 1.5 <1381, así que supongo que ese sería mi puntaje.

Perl - 94 caracteres, O (n log (n)) - Puntuación: 427

perl -wle '$n=1;$t=1;while($n<$ARGV[0]){$t++;if((1x$t)!~/^1?$|^(11+?)\1+$/){print $t;$n++;}}'

Python - 113 caracteres

import re
z = int(input())
n=1
t=1
while n<z:
    t+=1
    if not re.match(r'^1?$|^(11+?)\1+$',"1"*t):
        print t
        n+=1

AWK, 96 86 bytes

Subtítulo: ¡Mira mamá! ¡Solo agregando y algo de contabilidad!

Archivo fsoe3.awk:

{for(n=2;l<$1;){if(n in L)p=L[n]
else{print p=n;l++}
for(N=p+n++;N in L;)N+=p
L[N]=p}}

Correr:

$ awk -f fsoe3.awk <<< 5
2
3
5
7
11
$ awk -f fsoe3.awk <<< 1000 | wc -l
1000

BASH, 133 bytes

Archivo x.bash:

a=2
while((l<$1));do if((b[a]))
then((c=b[a]));else((c=a,l++));echo $a;fi;((d=a+c))
while((b[d]));do((d+=c));done
((b[d]=c,a++));done

Correr:

$ bash x.bash 5
2
3
5
7
11
$ bash x.bash 1000 | wc -l
1000

Las primas se calculan dejando que los números primos ya encontrados salten sobre la "cinta de enteros positivos". Básicamente es un tamiz serializado de Eratóstenes.

from time import time as t

L = {}
n = 2
l = 0

t0=t()

while l<1000000:

        if n in L:
                P = L[n]
        else:
                P = n
                l += 1
                print t()-t0

        m = n+P
        while m in L:
                m += P
        L[m] = P

        n += 1

... es el mismo algoritmo en Python e imprime el momento en que lse encontró la enésima prima en lugar de la prima en sí.

La salida graficada gnuplotproduce lo siguiente:

Los saltos probablemente tengan algo que ver con los retrasos de E / S de archivos debido a la escritura de datos almacenados en el disco ...

El uso de números mucho mayores de números primos para encontrar traerá demoras adicionales dependientes del sistema en el juego, por ejemplo, la matriz que representa la "cinta de enteros positivos" crece continuamente y tarde o temprano hará que cada computadora llore por más RAM (o intercambio posterior).

... así que tener una idea de la complejidad al observar los datos experimentales no ayuda mucho ... :-(

Ahora contando las adiciones necesarias para encontrar nprimos:

cells = {}
current = 2
found = 0

additons = 0

while found < 10000000:

        if current in cells:
                candidate = cells[current]
                del cells[current] # the seen part is irrelevant
        else:
                candidate = current
                found += 1 ; additons += 1
                print additons

        destination = current + candidate ; additons += 1
        while destination in cells:
                destination += candidate ; additons += 1
        cells[destination] = candidate

        current += 1 ; additons += 1

Scala 121 (99 sin el estándar de clase principal)

object Q extends App{Stream.from(2).filter{a=>Range(2,a).filter(a%_==0).isEmpty}.take(readLine().toInt).foreach(println)}

Python 3, 117106 bytes

Esta solución es ligeramente trivial, ya que genera 0 donde un número no es primo, pero lo publicaré de todos modos:

r=range
for i in[2]+[i*(not 0 in[i%j for j in r(3,int(i**0.5)+1,2)])for i in r(3,int(input()),2)]:print(i)

Además, no estoy seguro de cómo resolver la complejidad de un algoritmo. Por favor, no voten por esto. En cambio, sé amable y comenta cómo podría resolverlo. Además, dime cómo podría acortar esto.

Haskell (52² = 2704)

52`take`Data.List.nubBy(((1<).).gcd)[2..]`forM_`print

Perl 6, 152 bytes, O (n log n log (n log n) log (log (n log n))) (?), 9594.79 puntos

Según esta página , la complejidad de bits de encontrar todos los números primos hasta n es O (n log n log log n); la complejidad anterior usa el hecho de que la enésima prima es proporcional a n log n.

my \N=+slurp;my \P=N*(N.log+N.log.log);my @a=1 xx P;for 2..P.sqrt ->$i {if @a[$i] {@a[$_*$i]=0 for $i..P/$i}};say $_[1] for (@a Z ^P).grep(*[0])[2..N+1]

Groovy (50 Bytes) - O (n * sqrt (n)) - Puntuación 353.553390593

{[1,2]+(1..it).findAll{x->(2..x**0.5).every{x%it}}​}​

Toma n y genera todos los números del 1 al n que son primos.

El algoritmo que elegí solo genera primos n> 2, por lo que se requiere agregar 1,2 al principio.

Descompostura

x%it - Verdad implícita si no es divisible, falsa si lo es.

(2..x**0.5).every{...}- Para todos los valores entre 2 y sqrt (x), asegúrese de que no sean divisibles, para que esto devuelva verdadero, debe devolver verdadero para cada uno .

(1..it).findAll{x->...} - Para todos los valores entre 1 yn, encuentre todos los que se ajusten a los criterios de no ser divisible entre 2 y sqrt (n).

{[1,2]+...}​ - Agregue 1 y 2, porque siempre son primos y nunca están cubiertos por un algoritmo.

Raqueta 155 bytes

(let p((o'(2))(c 3))(cond[(>=(length o)n)(reverse o)][(ormap(λ(x)(= 0(modulo c x)))
(filter(λ(x)(<= x(sqrt c)))o))(p o(add1 c))][(p(cons c o)(add1 c))]))

Mantiene una lista de números primos encontrados y verifica la divisibilidad de cada número siguiente por números primos ya encontrados. Además, verifica solo hasta la raíz cuadrada del número que se está probando, ya que es suficiente.

Sin golf:

(define(nprimes n)
  (let loop ((outl '(2))                   ; outlist having primes being created
             (current 3))                  ; current number being tested
  (cond
    [(>= (length outl) n) (reverse outl)]  ; if n primes found, print outlist.
    [(ormap (λ(x) (= 0 (modulo current x))) ; test if divisible by any previously found prime
            (filter                         ; filter outlist till sqrt of current number
             (λ(x) (<= x (sqrt current)))
             outl))
     (loop outl (add1 current)) ]           ; goto next number without adding to prime list
    [else (loop (cons current outl) (add1 current))] ; add to prime list and go to next number
    )))

Pruebas:

(nprimes 35)

Salida:

'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149)

awk 45 (complejidad N ^ 2)

otro awk, para primos de hasta 100 uso como este

awk '{for(i=2;i<=sqrt(NR);i++) if(!(NR%i)) next} NR>1' <(seq 100)

código contado parte del golf es

{for(i=2;i<=sqrt(NR);i++)if(!(NR%i))next}NR>1

que se puede poner en un archivo de script y ejecutar como awk -f prime.awk <(seq 100)

Javascript, 61 caracteres

f=(n,p=2,i=2)=>p%i?f(n,p,++i):i==p&&n--&alert(p)||n&&f(n,++p)

Un poco peor que O (n ^ 2), se quedará sin espacio de pila para n grande.