Ihre Aufgabe ist es, ein Programm / eine Funktion zu schreiben, das / die eine ganze Zahl N als Eingabe akzeptiert, wenn Sie dies akzeptieren möchten. Das Programm / die Funktion sollte eine Liste der ersten N Primzahlen ausgeben / zurückgeben . Aber hier ist der Haken: Sie dürfen keine Primzahlen in Ihrem Code verwenden. Ein Primzeichen ist ein Zeichen, dessen Unicode-Codepunkt eine Primzahl ist. Im druckbaren ASCII-Bereich sind dies:

%)+/5;=CGIOSYaegkmq

Die Regel gilt jedoch auch für Nicht-ASCII-Zeichen, wenn Ihr Code diese verwendet.

• Eine gültige Eingabe ist eine Ganzzahl N mit 0 <N <= T , wobei Sie T auswählen können , sie muss jedoch größer oder gleich 10000 sein. T muss nicht endlich sein.
• Für ungültige Eingaben (Nicht-Ganzzahlen, Ganzzahlen außerhalb des Bereichs) eine Ausnahme auslösen oder "output / return nothing / null" ausgeben.
• Eine Ganzzahl mit führenden / nachfolgenden Leerzeichen als Eingabe wird als ungültig betrachtet.
• Eine Ganzzahl mit einem +Vorzeichen als Eingabe wird als ungültig betrachtet.
• Eine Ganzzahl mit führenden Nullen als Eingabe wird als gültig betrachtet.
• Wenn Sie in Ihrer Sprache eine bereits analysierte Ganzzahl als Eingabe übergeben können, gelten die obigen Analyseregeln (mit Ausnahme des Bereichs 1) nicht, da die Ganzzahl bereits analysiert wurde.
• Die Eingabe ist immer Base-10.
• Die Verwendung von eingebauten Primgeneratoren und Primalitätstestern (einschließlich Primfaktorisierungsfunktionen) ist nicht zulässig.
• Die Quellenbeschränkung gilt für Unicode-Zeichen, die Byte-Zählung für die Partitur kann jedoch auch in einer anderen Codierung erfolgen, wenn Sie dies wünschen.
• Die Ausgabe kann eine einzelne nachgestellte Zeile enthalten, dies ist jedoch nicht erforderlich.
• Wenn Sie die Primzahlliste als Zeichenfolge ausgeben / zurückgeben, muss jede Primzahl durch ein oder mehrere nichtstellige Zeichen begrenzt werden. Sie können auswählen, welches Trennzeichen Sie verwenden möchten.
• Dies ist eine Code-Golf- Herausforderung, der kürzeste Code in Bytes gewinnt.

Stapeln Sie Snippet, um Ihren Code zu überprüfen

Sie können das folgende Stack-Snippet verwenden, um zu überprüfen, ob Ihr Code keine Primzahlen enthält:

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

Probieren Sie es online aus.

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

Dies ist wahrscheinlich einer der schrecklich ineffizienten Algorithmen, die ich jemals implementiert habe. Aber ich habe es für die Größe getan!

Meine Antwort besteht aus einem Codeblock, der sich in CJam wie eine anonyme Funktion verhält. Führen Sie es mit einer Ganzzahl unmittelbar davor auf dem Stapel aus, und die resultierende Liste wird auf dem Stapel abgelegt. Ich behandle die obere Grenze der Eingabe als unendlich, damit ich diese Grenze nicht überprüfen muss.

Mein Algorithmus beginnt mit der Erhöhung von 3 auf die inputhöchste Potenz, die garantiert eine Zahl ergibt, die größer als die input-te Primzahl ist, wenn die Eingabe gültig ist. Dann wird eine Liste der ganzen Zahlen von 2 bis zu dieser Zahl minus eins erstellt, die groß genug ist, um alle gewünschten Primzahlen aufzunehmen. Um die zusammengesetzten Zahlen loszuwerden ... seufzen ... erstellen wir eine Liste aller paarweisen Produkte, die alle zusammengesetzten Zahlen von 4 bis zu einem für unsere Zwecke ausreichend großen Wert generieren sollten. Dann müssen Sie nur noch jedes Element aus der ursprünglichen Liste in dieser zusammengesetzten Liste entfernen, es auf die ersten inputElemente zuschneiden und die Elemente mit dem Zeilenvorschubzeichen verbinden.

Der Algorithmus sollte für jede Eingabe funktionieren. Es ist jedoch eine ganz andere Frage, ob der Dolmetscher / Computer über genügend Speicher oder Zeit verfügt, da der Zeit- und Platzbedarf in Bezug auf die Eingabe exponentiell ist. Wenn also die Eingabe für den Online-Dolmetscher größer als 5 oder für den Offline-Dolmetscher größer als 8 ist, lautet die Antwort auf diese Frage wahrscheinlich Nein.

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}

Übernimmt Eingaben über Funktionsargumente, Ausgaben über ausgelöste Ausnahmen.

Eingerückt:

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
}

Escapezeichen entfernt:

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

Erläuterung:

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.

Meine ursprüngliche Lösung verwendete eine returnAussage. Nachdem Sie diese Frage auf StackOverflow gestellt haben , regettman war er so freundlich, eine Möglichkeit zur Ausgabe / Rückgabe ohne Verwendung von bereitzustellen.

Vorschläge sind wie immer willkommen :)

Rubin, 74

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

Erläuterung:

*oInitialisiert ein leeres Ausgabearray. bis es nGegenstände gibt, finden wir die kleinste Zahl> = 2, die keinen Gegenstand teilt o, und fügen sie dann hinzu o. Um die Teilung zu testen, huch. Alle guten Operatoren sind unzulässig, und ich kann nicht einmal verwenden divmod. Das Beste, was ich sehen konnte, war die Verwendung von x.div yx geteilt durch y und abgerundet, dann multiplizieren Sie das mit y erneut. Wenn es gleich x ist, gab es keine Rundung, also dividiert y x. 1.>x.^ist ein Gleichheitstest, bei dem geprüft wird, ob das Ergebnis von xor 0 ist. Der .Vor-jedem-Operator liegt daran, dass Sie nicht mischen können. Operatoraufrufe ohne Klammern und Methodenaufrufe ohne Klammern .

Bearbeiten: Die Spezifikationen für die Bereichsprüfung wurden hinzugefügt, nachdem ich dies gepostet habe, denke ich. Zur Einhaltung sind 79 Zeichen erforderlich:

->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}*'<(~}

Probieren Sie es hier aus

Ich denke, dies sollte mit allen Regeln übereinstimmen und funktioniert für jedes nicht negative N (dh T ist unendlich). Es ist zwar schrecklich ineffizient, also versuchen Sie es nicht für große Zahlen.

Dies ist ein Block, der einer (unbenannten) Funktion am nächsten kommt. Er erwartet eine Ganzzahl auf dem Stapel, gibt alle Primzahlen aus und verlässt den Stapel ohne Eingabe. Für alle ungültigen Eingaben wird entweder ein Fehler ausgegeben oder es wird nichts gedruckt.

Der Großteil des Codes besteht aus der Validierung der Eingabe, gefolgt vom Sieb des Eratosthenes. Ich musste die Eingabebeschränkung nur an drei Stellen umgehen:

• )wird in CJam erhöht. Ich brauchte das einmal, konnte es aber durch ~(bitweise Ergänzung) ersetzen, weil ich die Zahlen danach sowieso quadrierte.
• %ist modulo. Ich benutze 37c~stattdessen, was zuerst den Charakter erstellt %und dann das auswertet. Das macht den Code viel langsamer.
• ;Öffnet und löscht ein Element aus dem Stapel. Ich muss das am Ende tun. Stattdessen benutze ich, '<(~was den Charakter schiebt <, dekrementiert und das bewertet.

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

Das war ziemlich knifflig. Einige Dinge, auf die ich gestoßen bin:

• Die meisten Schleifen ( whileund until) sind unbrauchbar, weil sie am ehesten mit doneeinem Shell-Schlüsselwort übereinstimmen und nicht das Ergebnis einer Variablenerweiterung sein können (es evalsei denn, sie werden verwendet, aber das ist auch nicht der Fall ). Die einzige verwendbare Schleife ist for/ in, die {/ }anstelle von do/ erlaubt done. for (( ; ; ))ist auch nicht verwendbar.
• =ist aus, also brauchen wir einen anderen Weg, um Variablen zuzuweisen. printf -vist gut dafür.
• Wir wissen, dass p (10000) 104729 ist, also können wir für die äußere Schleife für potenzielle Primzahlen einfach eine Schleife von 2 bis 104729 durchführen und brechen, sobald wir genug Primzahlen haben
• jotgeneriert die Liste der möglichen Faktoren in der inneren Schleife. Wenn ein möglicher Faktor eine mögliche Primzahl teilt, dann ist es keine Primzahl und wir brechen früh aus
• Glücklicherweise breakist eine Shell eingebaut und kein Schlüsselwort, so dass es als Ergebnis einer Erweiterung erzeugt werden kann. dcwandelt eine Zahl zur Basis 13 in den Bytestream umeak .
• Um zu überprüfen, ob ein potenzieller Faktor eine potenzielle Primzahl teilt, können wir die üblichen /oder %Shell-Arithmetikoperatoren nicht verwenden . Also das ist ausgelagert dcs - ~Operator, der Quotient und der Rest auf den Stapel schiebt.
• -lt - less-than - ist der einzige verwendbare Shell-Vergleichsoperator.
• echoist keine Verwendung für die Ausgabe. printffunktioniert aber solange wir vermeiden%

Es ist ein bisschen mühsam, die Eingabevalidierung richtig zu machen. Dies gibt bei ungültiger Eingabe nichts zurück.

Ausgabe:

$ ./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]]

Dies ist eine anonyme Funktion, die eine Ganzzahl nals Eingabe verwendet.

So funktioniert es: [p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]](Erstes Beispiel für Primzahl-Einzeiler im Haskell-Wiki, aber mit der elemersetzten Funktion) Erstellt eine unendliche Liste von Primzahlen. zipes mit den Zahlen von 1bis n, um eine Liste von (prime, seq. number)Paaren zu machen . Entfernen seq. Nummer wieder. Ergebnis ist eine Liste von Primzahlen der Länge n.

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

(Code wurde aufgrund der Zeichenbeschränkung abgeschnitten, vollständige Lösung hier )

Die folgenden Rostmerkmale sind aufgrund der Primäreinschränkung nicht mehr verfügbar:

• Funktionsaufrufe, wie sie benötigen ')'
• regelmäßige Bindungen, da sie let (e) erfordern
• Makrodefinitionen erfordern Makroregeln! (a, e, m)
• Übereinstimmungsanweisungen, sie erfordern Übereinstimmung (a, m) und => (=)
• Wandlungsfähigkeit, da diese immer mit dem Schlüsselwort mut (m) eingeleitet wird.
• return (e), break (a, e), continue (e)
• sonst (e)

Was Sie technisch nutzen können:

• ob. Aber ohne weiteres sind sie in Ausdruckskontexten nutzlos, also nur gut für Nebenwirkungen.
• Makros. Standardmakros wie Drucken! werden normalerweise von () gefolgt, aber es ist tatsächlich zulässig, stattdessen {} oder [] zu verwenden. Ohne dies wäre die Aufgabe unmöglich.
• Verschlüsse im engsten Sinne. Sie können sie nicht aufrufen (erfordert ()) oder binden (erfordert let), aber Sie können eine einzelne nicht-rekursive definieren. Ohne dies wäre die Aufgabe offensichtlich unmöglich geworden.
• structs.
• für Schleifen. Diese sind vielversprechend, da sie tatsächlich eine Variablenbindung ermöglichen und einen Iterator benötigen, der weiterhin mit der Bereichssyntax definiert werden kann. Der Iterator kann sogar ein Ausdruck sein.
• Eingebaute Operatoren, außer +,% und /. Die kurzschließenden logischen Operatoren scheinen vielversprechend.

Ich konnte mit diesen Werkzeugen einfach nichts Turing-komplettes machen. Es tut mir Leid. Es blieben nur die ersten 10000 Primzahlen, die von 5 gereinigt wurden. Zumindest können Sie es in Scheiben schneiden und haben eine gültige Lösung im engsten Sinne möglich.

Ich hätte gerne Experten für Turing-Tarpit-Tauchen (oder Rust!), Die mir sagten, ob ich etwas Besseres hätte tun können!

GNU APL, 75 68 67 65 59 56 55 Zeichen

⎕IOmuss sein 1.

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

Ich kam in diesen Monaten später wieder und stellte fest, dass ich einen zusätzlichen Platz hatte!

Pyth - 12 Bytes

Verwendet die Primfaktor-Funktion von pyth, um festzustellen, ob # eine Primzahl ist. Benutzt den !tPTTrick, der mir bei meiner Antwort für Primzahlen unter Million Problem vorgeschlagen wurde.

<f!tPTr2^T6Q

Da der Filter nur für Primzahlen unter n und nicht für die ersten n funktioniert, habe ich nur die Inverse von pi (x) für 10.000 nachgeschlagen und 104.000 erhalten, also verwende ich Primzahlen unter 10⁶ und erhalte die ersten n. Da dies nicht funktioniert, sollten Sie den Test durch Ersetzen ^T6mit ^T3und Beschränken von n auf unter 1000 ausführen . Eingabe von stdin und Ausgabe auf 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)