As regras são simples:

• Os primeiros n primos (não primos abaixo de n ) devem ser impressos na saída padrão separados por novas linhas (os primos devem ser gerados dentro do código)
• números primos não podem ser gerados por uma função embutida ou através de uma biblioteca , ou seja, o uso de uma função embutida ou de biblioteca como, por exemplo, prime = get_nth_prime (n), is_a_prime (number) ou factorlist = list_all_factors (number) não será muito criativo.

• Pontuação - digamos, definimos Pontuação = f ([número de caracteres no código]), O ( f (n)) sendo a complexidade do seu algoritmo em que n é o número de números primos encontrados. Portanto, por exemplo, se você tiver um código de 300 caracteres com complexidade O (n ^ 2), a pontuação é 300 ^ 2 = 90000 ; para 300 caracteres com O (n * ln (n)), a pontuação se torna 300 * 5,7 = 1711,13 ( vamos supor que todos os logs sejam logs naturais por simplicidade)

• Use qualquer linguagem de programação existente, menor pontuação ganha

Edit: Problema foi alterado de encontrar 'primeiros 1000000 primos' para 'primeiros n primos' por causa de uma confusão sobre o que 'n' em O (f (n)) é, n é o número de primos que você encontra (encontrar primos é o problema aqui e, portanto, a complexidade do problema depende do número de números primos encontrados)

Nota: para esclarecer algumas confusões sobre complexidade, se 'n' é o número de números primos que você encontra e 'N' é o enésimo número primo encontrado, a complexidade em termos de n é e N não é equivalente, ou seja, O (f (n))! = O (f (N)) como, f (N)! = Constante * f (n) e N! = Constante * n, porque sabemos que a enésima função primordial não é linear, pensei desde que estávamos descobrindo 'n' a complexidade dos primos deve ser facilmente expressável em termos de 'n'.

Conforme indicado pelo Kibbee, você pode visitar este site para verificar suas soluções ( aqui está a lista antiga do Google Docs)

Inclua-os na sua solução -

• qual a complexidade do seu programa (inclua análises básicas, se não triviais)

• comprimento do caractere do código

• a pontuação final calculada

Esta é minha primeira pergunta do CodeGolf, portanto, se houver um erro ou brecha nas regras acima, indique-as.

Python (129 caracteres, O (n * log log n), pontuação de 203.948)

Eu diria que a peneira de Eratóstenes é o caminho a percorrer. Muito simples e 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 aprimorado de antes.

Python ( 191 156 152 caracteres, O (n * log log n) (?), Pontuação de 252.620 (?))

Não consigo calcular a complexidade, esta é a melhor aproximação que posso 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)))é o limite superior do nth número primo.

Haskell, n ^ 1,1 taxa de crescimento empírico, 89 caracteres, pontuação 139 (?)

O seguinte funciona no prompt do GHCi quando a biblioteca geral que ele usa foi carregada anteriormente. Imprima n- ésima impressão , com base em 1:

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

Esta é uma peneira ilimitada de Eratóstenes, usando uma biblioteca de uso geral para listas ordenadas. Complexidade empírica entre 100.000 e 200.000 números primos O(n^1.1). Serve para O(n*log(n)*log(log n)).

Sobre estimativa de complexidade

Eu medi o tempo de execução para os primos 100k e 200k, depois calculei o logBase 2 (t2/t1)que foi produzido n^1.09. Definindo g n = n*log n*log(log n), calculando logBase 2 (g 200000 / g 100000)dá n^1.12.

Então 89**1.1 = 139, embora g(89) = 600. --- (?)

Parece que, para pontuar, a taxa de crescimento estimada deve ser usada em vez da função de complexidade em si. Por exemplo, g2 n = n*((log n)**2)*log(log n)é muito melhor que n**1.5, mas, para 100 caracteres, os dois produzem pontuação de 3239e 1000, respectivamente. Isso não pode estar certo. A estimativa no intervalo 200k / 100k fornece logBase 2 (g2 200000 / g2 100000) = 1.2e, portanto, pontuação de 100**1.2 = 251.

Além disso, não tento imprimir todos os números primos, apenas o n- ésimo primo.

Nenhuma importação, 240 caracteres. n ^ 1,15 taxa de crescimento empírico, pontuação 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), pontuação 7921

A pontuação mais alta por contagem de caracteres ganha, certo? Modificado para o primeiro N. Também, aparentemente, não posso usar uma calculadora, então minha pontuação não é tão ruim quanto eu pensava. (usando a complexidade da divisão de teste básico, conforme encontrado na fonte abaixo).

De acordo com Will Ness, o abaixo não é um programa Haskell completo (na verdade, ele depende do REPL). A seguir, é apresentado um programa mais completo com uma pseudo-peneira (as importações realmente salvam um caractere, mas eu não gosto de importações no código golf).

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

Esta versão é sem dúvida (n ^ 2). O algoritmo é apenas uma versão de golfe da ingênua `` peneira '', como visto aqui Old ghci 1 liner

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

Deixando a resposta antiga e enganosa porque a biblioteca à qual ele se vincula é bastante agradável.

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

Veja aqui uma implementação e os links para a complexidade do tempo. Infelizmente, as rodas têm um tempo de pesquisa de log (n), diminuindo a velocidade por um fator.

C #, 447 caracteres, bytes 452, pontuação?

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, Pontuação?

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

Se você instalar scriptscs, poderá executá-lo.

PS eu escrevi isso no Vim :D

GolfScript (45 caracteres, pontuação reivindicada ~ 7708)

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

Isso simplifica a divisão de teste por números primos. Se próximo da aresta de corte de Ruby (isto é, usando 1.9.3.0), a aritmética usa a multiplicação de Toom-Cook 3; portanto, uma divisão de teste é O (n ^ 1.465) e o custo total das divisões é O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)†. No entanto, no GolfScript, adicionar um elemento a uma matriz exige a cópia da matriz. Otimizei isso para copiar a lista de números primos somente quando encontrar um novo número primo, portanto, apenas o ntotal de vezes. Cada operação de cópia tem O(n)itens de tamanho O(ln(n ln n)) = O(ln n)†, dando O(n^2 ln n).

E é isso, meninos e meninas, por que o GolfScript é usado para jogar golfe, e não para programação séria.

† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). Eu deveria ter visto isso antes de comentar em várias postagens ...

Isso é tão fácil que até meu editor de texto pode fazer isso!

Vim: 143 pressionamentos de teclas (115 ações): O (n ^ 2 * log (n)): Pontuação: 101485.21

Submissão:

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 deve estar na primeira linha de um documento em branco. Após o término, cada sequência de 2 a N será uma linha separada.

Executando os comandos:

Primeiro, observe que qualquer comando com um sinal de intercalação na frente significa que você precisa pressionar Ctrl e digitar a próxima letra (por exemplo, ^ V é Ctrl-ve ^ R é Ctrl-r).

Isso substituirá qualquer coisa nos seus registros @a, @b, @dp.

Como isso usa qcomandos, não pode ser apenas colocado em uma macro. No entanto, aqui estão algumas dicas para executá-lo.

• qpqqdq apenas limpa registros
• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddcriará uma lista dos números 2 a N + 1. Esta é uma pausa entre as duas partes principais, portanto, uma vez feito isso, você não precisará fazer isso novamente
• 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@pprecisa ser digitado de uma só vez. Tente evitar o backspace, pois isso pode estragar tudo.
  • Se você cometer um erro, digite qdqqpqe tente esta linha novamente.

Para N grande, isso é muito lento. Demorou cerca de 27 minutos para executar N = 5000; considere-se avisado.

Algoritmo:

Isso usa um algoritmo recursivo básico para encontrar números primos. Dada uma lista de todos os números primos entre 1 e A, A + 1 é primo se não for divisível por nenhum dos números da lista de números primos. Comece em A = 2 e adicione números primos à lista à medida que são encontrados. Após N recursões, a lista conterá todos os números primos até N.

Complexidade

Esse algoritmo tem uma complexidade de O (nN), onde N é o número de entrada e n é o número de primos até N. Cada recursão testa n números e N são executadas, dando O (nN).

No entanto, N ~ n * log (n), fornecendo a complexidade final como O (n ² * log (n)) ( https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number )

Explicação

Não é fácil discernir o fluxo do programa a partir dos comandos vim, então eu o reescrevi no Python seguindo o mesmo fluxo. Assim como o código Vim, o código python irá errar quando chegar ao fim. Python não gosta de muita recursão; se você tentar esse código com N> 150 ou mais, ele atingirá a profundidade máxima de recursão

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

Agora, para dividir as teclas pressionadas!

• qpqqdqLimpa os registros @d @ @. Isso garantirá que nada seja executado ao configurar essas macros recursivas.

• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddTransforma a entrada em uma lista de números de 2 a N + 1. A entrada N + 1 é excluída como efeito colateral da configuração da macro @d.

  • Especificamente, grava uma macro que incrementa um número, depois a copia na próxima linha, depois grava 1 e executa essa macro N vezes.

• mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qgrava a macro @d, que implementa a função d () acima. As instruções "If" são interessantes de implementar no Vim. Usando o operador de pesquisa *, é possível escolher um determinado caminho a seguir. Quebrando o comando ainda mais temos

  • mpqdDefina a marca p aqui e comece a gravar a macro @d. A marca p precisa ser definida para que haja um ponto conhecido para o qual pular, pois isso é executado
  • o^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc> Grava o texto da instrução if / else
  • 0*w*wyiWdd@0 realmente executa a instrução if.
  • Antes de executar este comando, a linha conterá @a @b 0 0 `pj@p @a 0 (@a%@b) `pdd@p 0 `dj@d
  • 0 move o cursor para o início da linha

  • *w*w Move o cursor para o código para executar a próxima

    1. se @a == @b, ou seja `pj@p, que passa para o próximo número de @a e executa @p nele.
    2. se @a! = @b e @ a% @ b == 0, ou seja `pdd@p, que exclui o número atual @a, executa @p no próximo.
    3. se @a! = @b e @ a %% b! = 0, ou seja `dj@d, que verifica o próximo número para @b para ver se é um fator de @a

  • yiWdd@0 coloca o comando no registro 0, exclui a linha e executa o comando

  • q finaliza a gravação da macro @d

• Quando esta é executada pela primeira vez, o `pdd@pcomando é executado, excluindo a linha N + 1.

• qpmp"aywgg@dq grava a macro @p, que salva o número sob o cursor, depois vai para a primeira entrada e executa @d.

• gg@p na verdade, executa @p para que ele repita todo o arquivo.

QBASIC, 98 Caracteres, Complexidade N Sqrt (N), Pontuação 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

Atualizado para se adequar aos novos requisitos. 25% do código trata de encontrar um limite superior razoável para calcular números primos abaixo.

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

Eu também tenho uma peneira.

Aqui está um teste empírico dos custos de cálculo, sem o objetivo de análise:

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 

leva às seguintes contagens:

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

Não sei como calcular a pontuação. Vale a pena escrever mais 5 caracteres?

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 maior, reduz os cálculos em cerca de 16% nesse intervalo, mas, para a fórmula de pontuação, não consideramos fatores constantes?

novas considerações sobre o Big-O:

Para encontrar 1.000, 10.000, 100.000 números primos e assim por diante, eu uso uma fórmula sobre a densidade dos números primos x => (math.log (x) * x * 1.3, que determina o loop externo que estou executando.

Portanto, para os valores i em 1 a 6 => NPrimes (10 ^ i) executa 9399, 133768 ... vezes o loop externo.

Eu encontrei essa função O iterativamente com ajuda do comentário de Peter Taylor, que sugeriu um valor muito mais alto para exponenciação, em vez de 1,01, ele sugeriu 1,5:

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

O: (n: Int) Longo

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

Estes são os quocientes, se eu usar 1,01 como expoente. Aqui está o que o contador encontra empiricamente:

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

Os dois primeiros valores são discrepantes, porque eu faço uma correção constante para minha estimativa formular para valores pequenos (até 1000).

Com a sugestão de 1,5 de Peter Taylors, ficaria assim:

245.2396265560166
98.8566987153728
70.8831374743478
59.26104390040363
52.92941829568069
48.956394784317816

Agora, com o meu valor, chego a:

O(263)
res85: Long = 1576

Mas não tenho certeza, até que ponto posso chegar com minha função O aos valores observados.

Ruby 66 caracteres, O (n ^ 2) Pontuação - 4356

lazyestá disponível desde o Ruby 2.0 e 1.0/0é um truque interessante para obter um alcance infinito:

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

Ruby, 84 caracteres, 84 bytes, pontuação?

Este provavelmente é um pouco novato para essas partes, mas eu me diverti muito fazendo isso. Simplesmente faz um loop até que f(números primos encontrados) sejam iguais a n, o número desejado de números primos a serem encontrados.

A parte divertida é que, para cada loop, ele cria uma matriz de 2 a 1 a menos que o número que está sendo inspecionado. Em seguida, ele mapeia cada elemento da matriz para ser o módulo do número original e do elemento e verifica se algum dos resultados é zero.

Além disso, não tenho ideia de como pontuar.

Atualizar

O código compactou e incluiu um valor (totalmente arbitrário) 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

O i += 1bit and untilloop está meio que saltando para mim como áreas de melhoria, mas nessa faixa eu estou meio que preso. Enfim, foi divertido pensar.

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}

Divisão de teste simples até raiz quadrada. Portanto, a complexidade deve ser O (n ^ (1,5 + epsilon))

124 ^ 1,5 <1381, então essa seria minha pontuação, eu acho?

Perl - 94 caracteres, O (n log (n)) - Pontuação: 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

Legenda: Olha mamãe! Apenas adicionando e alguma contabilidade!

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

Corre:

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

BASH, 133 bytes

Arquivo 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

Corre:

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

Os primos são calculados deixando os números primos já encontrados saltarem na "fita de números inteiros positivos". Basicamente, é uma peneira serializada 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

... é o mesmo algoritmo em Python e imprime o momento em que o l-ésimo primo foi encontrado em vez do próprio primo.

A saída plotada com gnuplotproduz o seguinte:

Os saltos provavelmente têm algo a ver com atrasos de E / S do arquivo devido à gravação de dados em buffer no disco ...

O uso de números muito maiores de números primos para encontrar trará atrasos adicionais dependentes do sistema para o jogo, por exemplo, a matriz que representa a "fita de números inteiros positivos" cresce continuamente e, mais cedo ou mais tarde, todos os computadores clamam por mais RAM (ou troca posterior).

... então, ter uma idéia da complexidade observando os dados experimentais não ajuda muito ... :-(

Agora, contando as adições necessárias para encontrar nnúmeros primos:

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 sem o clichê da classe principal)

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

Python 3, 117 106 bytes

Esta solução é um pouco trivial, pois gera 0 onde um número não é primo, mas eu a publicarei de qualquer maneira:

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)

Além disso, não sei como resolver a complexidade de um algoritmo. Por favor, não diminua o voto por causa disso. Em vez disso, seja gentil e comente como eu poderia resolver isso. Além disso, diga-me como eu poderia reduzir isso.

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 pontos

De acordo com esta página , a complexidade de bits de localização de todos os números primos até n é O (n log n log log n); a complexidade acima usa o fato de que o enésimo nono primo é 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)) - Pontuação 353.553390593

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

Pega n e gera todos os números de 1 a n que são primos.

O algoritmo que escolhi produz apenas números primos n> 2, portanto é necessário adicionar 1,2 no início.

Demolir

x%it - Verdade implícita se não for divisível, falsidade se for.

(2..x**0.5).every{...}- Para todos os valores entre 2 e sqrt (x), verifique se eles não são divisíveis, para que isso retorne verdadeiro, deve retornar verdadeiro para todos .

(1..it).findAll{x->...} - Para todos os valores entre 1 e n, encontre todos os que atendam aos critérios de não ser divisível entre 2 e sqrt (n).

{[1,2]+...}​ - Adicione 1 e 2, porque eles são sempre primos e nunca são cobertos pelo algoritmo.

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

Ele mantém uma lista de números primos encontrados e verifica a divisibilidade de cada número seguinte por números primos já encontrados. Além disso, ele verifica apenas a raiz quadrada do número que está sendo testado, pois isso é suficiente.

Ungolfed:

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

Teste:

(nprimes 35)

Saída:

'(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 (complexidade N ^ 2)

outro awk, para primos de até 100, use assim

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

código de golfe contado parte é

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

que pode ser colocado em um arquivo de script e executado 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)

Um pouco pior que O (n ^ 2), ficará sem espaço de pilha para n grande.