Votre tâche, si vous choisissez de l'accepter, est d'écrire un programme / fonction qui accepte un entier N en entrée. Le programme / la fonction doit produire / renvoyer une liste des N premiers nombres premiers. Mais voici le hic: vous n'êtes pas autorisé à utiliser des caractères premiers dans votre code. Un caractère premier est un caractère dont le point de code Unicode est un nombre premier. Dans la gamme ASCII imprimable, ce sont:

%)+/5;=CGIOSYaegkmq

Mais la règle s'applique également aux caractères non ASCII si votre code les utilise.

• Une entrée valide est un entier N où 0 <N <= T , où vous pouvez choisir T , mais il doit être supérieur ou égal à 10000. T ne doit pas être fini.
• Pour les entrées non valides (non entiers, entiers hors limites), lève une exception ou génère / ne renvoie rien / null.
• Un entier avec des espaces de début / fin en entrée est considéré comme non valide.
• Un entier avec un +signe comme entrée est considéré comme non valide.
• Un entier avec des zéros de tête en entrée est considéré comme valide.
• Si votre langue vous permet de passer un entier déjà analysé en entrée, les règles d'analyse ci-dessus (à l'exception de la plage un) ne s'appliquent pas, car l'int est déjà analysé.
• L'entrée est toujours en base 10.
• L'utilisation de générateurs principaux et de testeurs de primalité intégrés (cela inclut les fonctions de factorisation principale) n'est pas autorisée.
• La restriction de source est imposée aux caractères Unicode, mais le comptage d'octets pour le score peut être dans un autre encodage si vous le souhaitez.
• La sortie peut contenir une seule nouvelle ligne de fin, mais ce n'est pas obligatoire.
• Si vous affichez / renvoyez la liste des nombres premiers sous forme de chaîne, chaque nombre premier doit être délimité par un ou plusieurs caractères non numériques. Vous pouvez choisir le délimiteur que vous utilisez.
• Il s'agit d'un défi de code-golf , le code le plus court en octets gagne.

Stack Snippet pour vérifier votre code

Vous pouvez utiliser l'extrait de pile ci-dessous pour vérifier que votre code ne contient pas de caractères principaux:

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 octets

Essayez-le en ligne.

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

C'est probablement l'un des algorithmes les plus horriblement inefficaces que j'ai jamais mis en œuvre. Mais je l'ai fait pour la taille!

Ma réponse consiste en un bloc de code, qui agit comme une fonction anonyme dans CJam. Exécutez-le avec un entier qui le précède immédiatement sur la pile et la liste résultante est transférée sur la pile. Je traite la limite supérieure de l'entrée comme infinie, je n'ai donc pas à vérifier cette limite.

Mon algorithme commence par élever 3 à la inputpuissance e, ce qui est garanti pour donner un nombre supérieur au input-ième nombre premier si l'entrée est valide. Ensuite, une liste des entiers de 2 à ce nombre moins un est générée, ce qui est une bande suffisamment grande pour contenir tous les nombres premiers que nous voulons. Pour se débarrasser des nombres composites ... soupir ... nous créons une liste de chaque produit par paire, qui devrait générer tous les nombres composites de 4 à une valeur stupidement grande, suffisamment grande pour nos besoins. Il suffit ensuite de supprimer chaque élément de la liste d'origine qui se trouve dans cette liste composite, de le réduire jusqu'aux premiers inputéléments et de joindre les éléments avec le caractère de nouvelle ligne.

L'algorithme devrait fonctionner pour n'importe quelle entrée. Cependant, la question de savoir si l'interprète / ordinateur a suffisamment de mémoire ou de temps est une toute autre question, car les exigences de temps et d'espace sont exponentielles par rapport à l'entrée. Donc, si l'entrée est supérieure à environ 5 pour l'interprète en ligne ou à environ 8 pour l'interprète hors ligne, la réponse à cette question est probablement non.

Java. 474 octets

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}

Prend l'entrée via l'argument de fonction, les sorties via l'exception levée.

Dentelé:

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
}

Caractères échappés supprimés:

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

Explication:

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.

Ma solution d'origine a utilisé une returndéclaration. Après avoir posé cette question sur StackOverflow, regettman a eu la gentillesse de fournir un moyen de sortie / retour sans utiliser de lettres majuscules.

Comme d'habitude, les suggestions sont les bienvenues :)

Rubis, 74

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

Explication:

*oinitialise un tableau de sortie vide. jusqu'à ce qu'il ait des néléments, nous trouvons le plus petit nombre> = 2 qui ne divise aucun élément actuellement o, puis ajoutez-le o. Pour tester la division, beurk. Tous les bons opérateurs sont interdits et je ne peux même pas les utiliser divmod. Le mieux que j'ai pu voir était d'utiliser x.div y, qui prend x divisé par y et arrondit vers le bas, puis multiplier à nouveau par y. S'il est égal à x, il n'y a pas eu d'arrondi, donc y divise x. 1.>x.^est un test d'égalité, vérifiant si le résultat de xor est 0. L' .avant chaque opérateur est parce que vous ne pouvez pas mélanger les .appels d'opérateur sans-parent et les appels de méthode sans parenthèses.

Edit: Les spécifications de vérification de portée ont été ajoutées après avoir posté cela, je pense. Pour se conformer, il faut 79 caractères:

->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 octets

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

Essayez-le ici

Je pense que cela devrait respecter toutes les règles et fonctionne pour tout N non négatif (c'est-à-dire que T est infini). C'est horriblement inefficace, alors ne l'essayez pas pour un grand nombre.

Il s'agit d'un bloc - la chose la plus proche d'une fonction (sans nom) - qui attend un entier sur la pile, imprime tous les nombres premiers et laisse la pile sans son entrée. Pour toutes les entrées invalides, il générera une erreur ou n'imprimera rien.

La plupart du code est la validation des entrées, suivie du tamis d'Eratosthène. Je n'avais besoin de contourner la restriction d'entrée qu'à 3 endroits:

• )est incrément dans CJam. J'avais besoin de cela une fois, mais je pouvais le remplacer par ~(complément au niveau du bit) parce que je mettais les chiffres au carré par la suite de toute façon.
• %est modulo. J'utilise à la 37c~place, ce qui crée d'abord le personnage %, puis l'évaluation. Cela rend le code beaucoup plus lent.
• ;saute et rejette un élément de la pile. Je dois le faire à la fin. Au lieu de cela, j'utilise '<(~ce qui pousse le caractère <, le décrémente et évalue ça.

Bash + coreutils, 227 octets

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

C'était assez délicat. Certaines choses que j'ai rencontrées:

• La plupart des boucles ( whileet until) sont inutilisables car elles se rapprochent le plus d' doneun mot-clé shell et ne peuvent pas être le résultat d'une expansion de variable (sauf si elle evalest utilisée, mais elle l'est également). La seule boucle utilisable est for/ inqui autorise {/ }au lieu de do/ done. for (( ; ; ))n'est pas non plus utilisable.
• =est sorti, nous avons donc besoin d'une autre façon d'affecter des variables. printf -vest bon pour cela.
• Nous savons que p (10000) est 104729, donc pour la boucle externe des nombres premiers potentiels, nous pouvons simplement boucler de 2 à 104729 et rompre une fois que nous avons suffisamment de nombres premiers
• jotgénère la liste des facteurs potentiels dans la boucle interne. Si un facteur potentiel divise un potentiel premier, il n'est pas premier et nous éclatons tôt
• Heureusement, il breaks'agit d'un shell intégré et non d'un mot-clé, il peut donc être généré à la suite d'une expansion. dcconvertit un nombre de base 13 en bytestream eak.
• Pour vérifier si un facteur potentiel divise un nombre premier potentiel, nous ne pouvons pas utiliser les opérateurs arithmétiques habituels /ou %shell. C'est donc sous-traité à l' opérateur dcs ~, qui pousse le quotient et le reste vers la pile.
• -lt - less-than - est le seul opérateur de comparaison de shell utilisable.
• echoest inutile pour la sortie. printffonctionne bien aussi longtemps que nous évitons%

Obtenir la bonne validation d'entrée est un peu pénible. Cela ne renvoie rien en cas d'entrée invalide.

Sortie:

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

Haskell, 90 octets

\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]]

Il s'agit d'une fonction anonyme qui prend un entier nen entrée.

Comment ça marche: [p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]](premier exemple de nombres premiers sur le wiki Haskell mais avec la elemfonction remplacée) crée une liste infinie de nombres premiers. zipavec les nombres de 1à npour faire une liste de (prime, seq. number)paires. Supprimer le seq. encore une fois. Le résultat est une liste de nombres premiers de longueur n.

Rouille, 64897 octets

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

(code coupé en raison de la limite de caractères, solution complète ici )

Les caractéristiques de rouille suivantes deviennent indisponibles en raison de la restriction principale:

• appels de fonction, car ils nécessitent ')'
• reliures régulières, car elles nécessitent let (e)
• les définitions de macro, elles nécessitent des macro-règles! (a, e, m)
• correspond aux instructions, elles nécessitent une correspondance (a, m) et => (=)
• mutabilité, car il est toujours introduit avec le mot-clé mut (m).
• return (e), break (a, e), continue (e)
• sinon (e)

Ce que vous pouvez utiliser techniquement:

• si. Mais sans rien d'autre, ils sont inutiles dans les contextes d'expression, donc seulement bons pour les effets secondaires.
• macros. Macros standard comme impression! sont généralement suivis de (), mais il est en fait légal d'utiliser {} ou [] à la place. Sans cela, la tâche serait impossible.
• fermetures, au sens le plus étroit. Vous ne pouvez pas les appeler (requiert ()) ou les lier (nécessite let), mais vous pouvez en définir un seul non récursif. Sans cela, la tâche deviendrait évidemment impossible.
• structs.
• pour les boucles. Celles-ci sont prometteuses, car elles permettent en fait la liaison de variables, et elles prennent un itérateur, qui peut toujours être défini avec la syntaxe de la plage. L'itérateur peut même être une expression.
• Opérateurs intégrés, sauf +,% et /. Les opérateurs logiques de court-circuit semblent prometteurs.

Je ne pouvais tout simplement rien faire de Turing avec ces outils. Je suis désolé. Il ne restait plus qu'à inclure les 10000 premiers nombres premiers, nettoyés de 5. Au moins, vous pouvez le découper et avoir une solution valable, dans le sens le plus étroit possible.

J'aimerais beaucoup que des experts en plongée tarpit Turing (ou en rouille!) Me disent si j'aurais pu faire mieux!

GNU APL, 75 68 67 65 59 56 55 caractères

⎕IOdoit être 1.

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

Je suis revenu ce mois plus tard en réalisant que j'avais un espace supplémentaire!

Pyth - 12 octets

Utilise la fonction de factorisation principale de pyth pour voir si # est premier. Utilise l' !tPTastuce qui m'a été suggérée lors de ma réponse pour les nombres premiers sous un problème d'un million.

<f!tPTr2^T6Q

Étant donné que le filtre ne fonctionne que pour les nombres premiers sous n et non pas les premiers n, j'ai simplement recherché l'inverse de pi (x) pour 10 000 et obtenu 104 000, donc j'utilise des nombres premiers sous 10⁶ et j'obtiens le premier n. Cela ne fonctionne pas réellement, vous devez donc tester en remplaçant ^T6par ^T3et restreindre n à moins de 1000. Entrée depuis stdin et sortie vers 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)