Sua tarefa, se você optar por aceitá-la, é escrever um programa / função que aceite um número inteiro N como entrada. O programa / função deve gerar / retornar uma lista dos primeiros N números primos. Mas aqui está o problema: você não tem permissão para usar caracteres primos no seu código. Um caractere primo é um caractere cujo ponto de código Unicode é um número primo. No intervalo de impressão ASCII, são eles:

%)+/5;=CGIOSYaegkmq

Mas a regra também se aplica a caracteres não ASCII se o seu código os usar.

• Uma entrada válida é um número inteiro N, onde 0 <N <= T , onde você pode escolher T , mas deve ser maior ou igual a 10000. T não precisa ser finito.
• Para entradas inválidas (não-inteiros, inteiros fora do intervalo), lance uma exceção ou produza / retorna nada / nulo.
• Um número inteiro com espaço em branco à esquerda / à esquerda como entrada é considerado inválido.
• Um número inteiro com um +caractere como sinal como entrada é considerado inválido.
• Um número inteiro com zeros à esquerda como entrada é considerado válido.
• Se o seu idioma permitir que você passe um número inteiro já analisado como entrada, as regras de análise acima (exceto o intervalo um) não se aplicam, porque o int já foi analisado.
• A entrada é sempre a base 10.
• Não é permitido o uso de geradores primos e testadores de primalidade embutidos (isso inclui funções de fatoração primária).
• A restrição de origem é imposta aos caracteres Unicode, mas a contagem de bytes para a pontuação pode estar em outra codificação, se desejar.
• A saída pode conter uma única nova linha à direita, mas isso não é necessário.
• Se você produzir / retornar a lista de números primos como uma sequência, todos os números primos deverão ser delimitados por um ou vários caracteres não digitados. Você pode escolher qual delimitador você usa.
• Este é um desafio de código-golfe , o código mais curto em bytes vence.

Snippet de pilha para verificar seu código

Você pode usar o Snippet de pilha abaixo para verificar se seu código não contém caracteres principais:

var primes=[],max=10000;for(var i=2;i<=max;i++){primes.push(i);}for(var N=2;N<Math.sqrt(max);N++){if(primes.indexOf(N)===-1){continue;}primes=primes.filter(function (x){return x===N||x%N!==0;});}function setText(elem,text){var z=('innerText' in elem)? 'innerText' : 'textContent';elem[z]=text;}function verify(inputCode,resultSpan){var invalidChars=[];var success=true;for(var i=0;i<inputCode.length;i++){var cc = inputCode.charCodeAt(i);if (cc>max){setText(resultSpan,"Uh oh! The char code was bigger than the max. prime number calculated by the snippet.");success = false;break;}if (primes.indexOf(cc)!==-1){invalidChars.push(inputCode[i]);}}if (invalidChars.length===0&&success){setText(resultSpan, "Valid code!");}else if(success) {  var uniqueInvalidChars = invalidChars.filter(function (x, i, self){return self.indexOf(x)===i;});setText(resultSpan, "Invalid code! Invalid chars: " + uniqueInvalidChars.join(""));    }}document.getElementById("verifyBtn").onclick=function(e){e=e||window.event;e.preventDefault();var code=document.getElementById("codeTxt").value;verify(code,document.getElementById("result"));};

Enter your code snippet here:<br /><textarea id="codeTxt" rows="5" cols="70"></textarea><br /><button id="verifyBtn">Verify</button><br /><span id="result"></span>

CJam, 19 18 30 34 33 19 17 21 20 bytes

Experimente online.

{_3\#,2>__ff*:~-<N*}

Este é provavelmente um dos algoritmos mais terrivelmente ineficientes que já implementei. Mas eu fiz isso pelo tamanho!

Minha resposta consiste em um bloco de código, que age como uma função anônima no CJam. Execute-o com um número inteiro imediatamente anterior à pilha e a lista resultante é despejada na pilha. Trato o limite superior da entrada como infinito, para que não precise verificar esse limite.

Meu algoritmo começa aumentando 3 à inputpotência th, que é garantida para fornecer um número maior que o input-ésimo primo, se a entrada for válida. Em seguida, é gerada uma lista dos números inteiros de 2 a esse número menos um, o que é uma faixa grande o suficiente para conter todos os números primos que queremos. Para se livrar dos números compostos ... suspiro ... criamos uma lista de todos os produtos aos pares, que devem gerar todos os números compostos de 4 a um valor estupidamente grande, grande o suficiente para nossos propósitos. Depois, basta remover todos os elementos da lista original desta lista composta, apará-los até os primeiros inputelementos e unir os elementos ao caractere de nova linha.

O algoritmo deve funcionar para qualquer entrada. No entanto, se o intérprete / computador tem ou não memória ou tempo suficiente é outra questão, porque os requisitos de tempo e espaço são exponenciais em relação à entrada. Portanto, se a entrada for maior que cerca de 5 para o intérprete on-line ou cerca de 8 para o off-line, a resposta a essa pergunta provavelmente será não.

Java. 474 bytes

i\u006dport j\u0061v\u0061.util.*\u003bvoid b(int b\u0029{Lon\u0067 c\u003d2L,d,f[]\u003d{}\u003bfor(f\u003dArr\u0061ys.copy\u004ff(f,b\u0029,Arr\u0061ys.fill(f,0L\u0029\u003bb-->0\u003b\u0029for(d\u003d0L\u003bf[b]<1\u003bf[b]\u003dd<1?c:f[b],d\u003d0L,c\u002b\u002b\u0029for(lon\u0067 h:f\u0029d\u003dh>0&&c\u002fh*h\u003d\u003dc?1:d\u003bj\u0061v\u0061x.x\u006dl.bind.JAXB.un\u006d\u0061rsh\u0061l(""\u002bArr\u0061ys.\u0061sList(f\u0029,Lon\u0067.cl\u0061ss\u0029\u003b}

Recebe entrada via argumento de função, sai via exceção lançada.

Recuado:

i\u006dport j\u0061v\u0061.util.*\u003b
void b(int b\u0029{
    Lon\u0067 c\u003d2L,d,f[]\u003d{}\u003b
    for(f\u003dArr\u0061ys.copy\u004ff(f,b\u0029,Arr\u0061ys.fill(f,0L\u0029\u003bb-->0\u003b\u0029
        for(d\u003d0L\u003bf[b]<1\u003bf[b]\u003dd<1?c:f[b],d\u003d0L,c\u002b\u002b\u0029
            for(lon\u0067 h:f\u0029
                d\u003dh>0&&c\u002fh*h\u003d\u003dc?1:d\u003b
    j\u0061v\u0061x.x\u006dl.bind.JAXB.un\u006d\u0061rsh\u0061l(""\u002bArr\u0061ys.\u0061sList(f\u0029,Lon\u0067.cl\u0061ss\u0029\u003b
}

Caracteres escapados removidos:

import java.util.*;
void b(int b){
    Long c=2L,d,f[]={};
    for(f=Arrays.copyOf(f,b),Arrays.fill(f,0L);b-->0;)
        for(d=0L;f[b]<1;f[b]=d<1?c:0,d=0L,c++)
            for(long h:f)
                d=h>0&&c/h*h==c?1:d;
    javax.xml.bind.JAXB.unmarshal(""+Arrays.asList(f),Long.class);
}

Explicação:

Long c,d,f[]={};                                                //Initialize variables.

for(f=java.util.Arrays.copyOf(f,b),Arrays.fill(f,0L);b-->0;)
    f=java.util.Arrays.copyOf(f,b),Arrays.fill(f,0L)            //Initialize f to an array of 0's.
                                                     b-->0      //Iterate over the first b primes.

for(d=0L;f[b]<1;f[b]=d<1?c:0,d=0L,c++)
    d=0L                        d=0L                            //Initialize d to 0.
         f[b]<1                      c++                        //Increment c while the b'th prime is 0.
                f[b]=d<1?c:0                                    //If d = 0, the b'th prime = c, else continue.

for(long h:f)                                                   //Iterate over all found primes.

d=h>0&&c/h*h==c?1:d;
  h>0                                                           //Ignore non-found primes.
       c/h*h==c                                                 //Equivalent to c%h==0
               ?1:d                                             //If h is prime and c is divisible by h, d = 1. Otherwise d stays unchanged.

javax.xml.bind.JAXB.unmarshal(""+Arrays.asList(f),Long.class)   //Print solution to stderr
javax.xml.bind.JAXB.unmarshal(                   ,Long.class)   //Prints what's contained to stderr.
                                 Arrays.asList(f)               //Convert f to list.
                              ""+                               //Convert to string.

Minha solução original usou uma returndeclaração. Depois de fazer essa pergunta no StackOverflow, regettman teve a gentileza de fornecer uma maneira de gerar / retornar sem usar letras maiúsculas.

Como sempre, sugestões são bem-vindas :)

Ruby, 74

->n,*o{o<<[2..n*n][0].find{|x|!o.find{|y|1.>x.^y.*x.div y}}until o[n-1]
o}

Explicação:

*oinicializa uma matriz de saída vazia. até que ele tenha nitens, encontramos o menor número> = 2 que não divide nenhum item no momento oe o adicionamos a o. Para testar a divisão, caramba. Todos os bons operadores são proibidos, e eu nem posso usar divmod. O melhor que pude ver foi usar x.div y, que pega x dividido por y e arredonda para baixo, depois multiplica por y novamente. Se for igual a x, não houve arredondamento, então y divide x. 1.>x.^é um teste de igualdade, verificando se o resultado de xor é 0. O .antes de todo operador é porque você não pode misturar .chamadas de operadores livres e chamadas de método sem parênteses.

Edit: As especificações de verificação de faixa foram adicionadas depois que eu postei isso, eu acho. Para cumprir requer 79 caracteres:

->n,*o{o<<[*2..-~n*n].find{|x|!o.find{|y|1.>x.^y.*x.div y}}until o[n-1]||n<1
o}

CJam, 38 37 30 bytes

{_~2#,2>\{(\{1$37c~},\p}*'<(~}

Experimente aqui

Eu acho que isso deve estar em conformidade com todas as regras e funciona para qualquer N não negativo (ou seja, T é infinito). É terrivelmente ineficiente, portanto, não tente por grandes números.

Este é um bloco - a coisa mais próxima de uma função (sem nome) - que espera um número inteiro na pilha, imprime todos os números primos e deixa a pilha sem sua entrada. Para todas as entradas inválidas, ele gera um erro ou imprime nada.

A maior parte do código é validação de entrada, seguida pela peneira de Eratóstenes. Eu só precisava solucionar a restrição de entrada em 3 locais:

• )é incremento no CJam. Eu precisei disso uma vez, mas poderia substituí-lo por ~(complemento bit a bit) porque, ao mesmo tempo, estava quadrando os números.
• %é módulo. Em 37c~vez disso, estou usando , o que primeiro cria o personagem %e depois avalia. Isso torna o código muito mais lento.
• ;aparece e descarta um elemento da pilha. Eu preciso fazer isso no final. Em vez disso, estou usando o '<(~que empurra o personagem <, o diminui e o avalia.

Bash + coreutils, 227 bytes

printf -vb br`dc<<<Di14B8209P`
printf -vc -- $[$1-0]
[ "${1#$c}" -o $c -lt 1 ]||{
for i in {2..104729}
{
for f in `jot $[i-1] $[i-1] 1`
{
[ 0 -lt `dc<<<"$i $f~p"` ]||$b
}
[ $f -lt 2 ]&&printf $i\ &&: $[c--]
[ $c -lt 1 ]&&$b
}
}

Isso foi bastante complicado. Eu encontrei algumas coisas:

• A maioria dos loops ( whilee until) é inutilizável porque é mais próxima da donequal é uma palavra-chave shell e não pode ser o resultado de uma expansão variável (a menos que evalseja usada, mas que também esteja fora). O único loop utilizável é for/ inque permite {/ em }vez de do/ done. for (( ; ; ))também não é utilizável.
• =está fora, então precisamos de outra maneira de atribuir variáveis. printf -vé bom para isso.
• Sabemos que p (10000) é 104729, portanto, para o loop externo para números primos em potencial, podemos simplesmente fazer um loop de 2 a 104729 e interromper quando tivermos números primos suficientes
• jotgera a lista de fatores potenciais no loop interno. Se um fator potencial divide um primo em potencial, ele não é primo e iniciamos cedo
• Felizmente, breaké um shell embutido e não uma palavra-chave; portanto, pode ser gerado como resultado de uma expansão. dcconverte um número base 13 no bytestream eak.
• Para verificar se um fator potencial divide um primo potencial, não podemos usar os operadores aritméticos usuais /ou %shell. Portanto, isso é terceirizado para dco ~operador s , que envia o quociente e o restante para a pilha.
• -lt - menor que - é o único operador de comparação de shell utilizável.
• echonão serve para saída. printffunciona embora contanto que evitemos%

Acertar a validação de entrada é um pouco trabalhoso. Isso não retorna nada no caso de entrada inválida.

Saída:

$ ./primenoprime.sh 10
2 3 5 7 11 13 17 19 23 29 $ 

Haskell, 90 bytes

\n->[fst c|c<-zip[p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]][1..n]]

Esta é uma função anônima que recebe um número inteiro ncomo entrada.

Como funciona: [p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]](o primeiro exemplo de linhas principais número um no wiki de Haskell, mas com a elemfunção substituída) cria uma lista infinita de números primos. zipcom os números de 1a npara fazer uma lista de (prime, seq. number)pares. Remova seq. número, novamente. Resultado é uma lista de números primos de comprimento n.

Ferrugem, 64897 bytes

|n|println!{"{:?}",&[2,3,6-1,7,11,13,17,19,23,29,31,37,41,43,47,60-7,0x3b,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,0x97,0x9d,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,0xfb,0x101 ...}

(código cortado devido ao limite de caracteres, solução completa aqui )

Os seguintes recursos de ferrugem ficam indisponíveis devido à restrição principal:

• chamadas de função, pois requerem ')'
• ligações regulares, uma vez que exigem let (e)
• definições de macro, eles exigem regras de macro! (a, e, m)
• instruções match, elas exigem match (a, m) e => (=)
• mutabilidade, uma vez que é sempre introduzida com a palavra-chave mut (m).
• retornar (e), interromper (a, e), continuar (e)
• mais (e)

O que você pode usar tecnicamente:

• E se. Mas sem mais nada, eles são inúteis em contextos de expressão, então são bons apenas para efeitos colaterais.
• macros. Macros padrão como impressão! geralmente são seguidos por (), mas é realmente legal usar {} ou []. Sem isso, a tarefa seria impossível.
• fechamentos, no sentido mais restrito. Você não pode chamá-los (requer ()) ou vinculá-los (requer deixar), mas pode definir um único não-recursivo. Sem isso, a tarefa obviamente se tornaria impossível.
• estruturas.
• para loops. Eles são promissores, pois permitem a ligação de variáveis ​​e levam um iterador, que ainda pode ser definido com a sintaxe do intervalo. O iterador pode até ser uma expressão.
• Operadores internos, exceto +,% e /. Os operadores lógicos em curto-circuito parecem promissores.

Eu simplesmente não conseguia fazer nada completo de Turing com essas ferramentas. Eu sinto Muito. Tudo o que restava era incluir os primeiros 10000 primos completos, limpos de 5. Pelo menos você pode cortá-lo e ter uma solução válida, no sentido mais restrito possível.

Eu gostaria muito que os especialistas em mergulho no tarpit de Turing (ou no Rust!) Me dissessem se eu poderia ter feito algo melhor!

GNU APL, 75 68 67 65 59 56 55 caracteres

⎕IOdeve ser 1.

∇z←p n
z←2,j←3
j←j--2
→2×⍳∨⌿1>z|j
z←z,j
→2×⍳n>⍴z
z←n↑z∇

Voltei meses depois, percebendo que tinha um espaço extra!

Pitão - 12 bytes

Usa a função de fatoração principal de pyth para ver se # é primo. Usa o !tPTtruque sugerido para mim na minha resposta para problemas com números primos abaixo de um milhão.

<f!tPTr2^T6Q

Como o filtro funciona apenas para números primos abaixo de n e não no primeiro n, eu apenas procurei o inverso de pi (x) para 10.000 e obtive 104.000, então eu uso números primos abaixo de 10⁶ e obtive o primeiro n. Na verdade, isso não é executado; portanto, você deve testar substituindo ^T6por ^T3e restringindo n abaixo de 1000. Entrada de stdin e saída para stdout.

<          Q     Slice first n
f     r2^T6      filter on range 2->10⁶
 !               Logical not (gives true if tail is empty)
  t              Tail (all but first, so gives empty if prime fact is len 1)
   PT            Prime factorization of filter var (len 1 if num is prime)