Twoim zadaniem, jeśli zdecydujesz się go zaakceptować, jest napisanie programu / funkcji, która przyjmuje liczbę całkowitą N jako dane wejściowe. Program / funkcja powinna wypisać / zwrócić listę pierwszych N liczb pierwszych. Ale oto haczyk: nie wolno używać znaków pierwszych w kodzie. Znak główny to znak, którego punkt kodu Unicode jest liczbą pierwszą. W zakresie ASCII do wydruku są to:

%)+/5;=CGIOSYaegkmq

Ale reguła ma również zastosowanie do znaków spoza ASCII, jeśli Twój kod ich używa.

• Poprawnym wejściem jest liczba całkowita N, gdzie 0 <N <= T , gdzie można wybrać T , ale musi ona być większa lub równa 10000. T nie musi być skończone.
• W przypadku niepoprawnych danych wejściowych (wartości nie będące liczbami całkowitymi, liczby całkowite poza zakresem) wyrzuć wyjątek lub wyślij / wyślij nic / null.
• Liczba całkowita z wiodącymi / końcowymi białymi znakami wejściowymi jest uważana za niepoprawną.
• Liczba całkowita ze +znakiem jako znak wejściowy jest uważana za niepoprawną.
• Liczba całkowita z wiodącymi zerami na wejściu jest uważana za prawidłową.
• Jeśli Twój język pozwala na przekazanie już przeanalizowanej liczby całkowitej jako danych wejściowych, powyższe reguły analizy (z wyjątkiem zakresu 1) nie mają zastosowania, ponieważ int jest już przeanalizowany.
• Dane wejściowe zawsze mają wartość base-10.
• Korzystanie z wbudowanych generatorów liczb pierwszych i testerów pierwotności (w tym funkcji faktoryzacji liczb pierwszych) jest niedozwolone.
• Ograniczenie źródła jest nakładane na znaki Unicode, ale liczenie bajtów na wynik może być w innym kodowaniu, jeśli chcesz.
• Dane wyjściowe mogą zawierać pojedynczy znak nowej linii, ale nie jest to wymagane.
• Jeśli wypiszesz / zwrócisz listę liczb pierwszych jako ciąg znaków, to każda liczba pierwsza musi być oddzielona jednym lub wieloma niecyfrowymi znakami. Możesz wybrać używany ogranicznik.
• Jest to wyzwanie dla golfa , wygrywa najkrótszy kod w bajtach.

Stos Snippet, aby zweryfikować kod

Możesz użyć poniższego fragmentu stosu, aby sprawdzić, czy Twój kod nie zawiera znaków pierwszych:

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 bajtów

Wypróbuj online.

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

Jest to prawdopodobnie jeden z najbardziej okropnie nieefektywnych algorytmów, jakie kiedykolwiek wdrożyłem. Ale zrobiłem to dla wielkości!

Moja odpowiedź składa się z bloku kodu, który działa jak anonimowa funkcja w CJam. Uruchom go z liczbą całkowitą bezpośrednio poprzedzającą go na stosie, a wynikowa lista zostanie zrzucona na stos. Górną granicę na wejściu traktuję jako nieskończoną, więc nie muszę jej sprawdzać.

Mój algorytm zaczyna się od podniesienia 3 do inputtej potęgi, co gwarantuje, że da liczbę większą niż input-ta liczba pierwsza, jeśli dane wejściowe są prawidłowe. Następnie generowana jest lista liczb całkowitych od 2 do tej liczby minus jeden, która jest wystarczająco dużym pokosem, aby pomieścić wszystkie pożądane liczby pierwsze. Aby pozbyć się liczb zespolonych ... westchnienie ... tworzymy listę każdego produktu parami, który powinien wygenerować wszystkie liczby zespolone od 4 do jakiejś głupiej dużej wartości, wystarczająco dużej dla naszych celów. Następnie wystarczy usunąć każdy element z oryginalnej listy, która znajduje się na tej liście złożonej, i przyciąć go do pierwszegoinput elementów i połączyć elementy znakiem nowej linii.

Algorytm powinien działać dla każdego wejścia. Jednak to, czy tłumacz / komputer ma wystarczającą ilość pamięci lub czasu, to zupełnie inne pytanie, ponieważ wymagania dotyczące czasu i miejsca są wykładnicze w stosunku do danych wejściowych. Jeśli więc wkład jest większy niż około 5 dla tłumacza online lub około 8 dla tłumacza offline, wówczas odpowiedź na to pytanie jest prawdopodobnie nie.

Jawa. 474 bajty

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}

Pobiera dane wejściowe za pomocą argumentu funkcji, dane wyjściowe przez zgłoszony wyjątek.

Zębaty:

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
}

Usunięte znaki ucieczki:

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

Wyjaśnienie:

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.

Moje oryginalne rozwiązanie wykorzystało returnoświadczenie. Po zadaniu tego pytania na StackOverflow, regettman był na tyle miły, że zapewnił sposób wyjścia / zwrotu bez użycia pierwszych liter.

Jak zwykle sugestie są mile widziane :)

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}

Wyjaśnienie:

*oinicjuje pustą tablicę wyjściową. dopóki nie będzie zawierał nprzedmiotów, znajdziemy najmniejszą liczbę> = 2, która nie dzieli obecnie żadnego elementu o, a następnie dodajemy go o. Aby sprawdzić podział, chłopaki. Wszyscy dobrzy operatorzy są niedozwoleni i nawet nie mogę z nich korzystać divmod. Najlepsze, co mogłem zobaczyć, to użyć x.div y, która bierze x podzielone przez y i zaokrągla w dół, a następnie pomnoży to ponownie przez y. Jeśli jest równy x, nie było zaokrąglenia, więc y dzieli x. 1.>x.^jest testem równości, sprawdzającym, czy wynik xor wynosi 0. .Przed każdym operatorem jest to, że nie można mieszać. wywołań operatora wolnych od nawiasów i wywołań metod bez nawiasów.

Edycja: Myślę, że specyfikacje sprawdzania zasięgu zostały dodane po tym, jak to opublikowałem. Do spełnienia wymaga 79 znaków:

->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 bajtów

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

Wypróbuj tutaj

Myślę, że powinno to być zgodne ze wszystkimi zasadami i działa dla każdego nieujemnego N (tj. T jest nieskończony). Jest to jednak okropnie nieefektywne, więc nie próbuj tego w przypadku dużych liczb.

Jest to blok - najbliższy funkcji (nienazwanej) - która oczekuje liczby całkowitej na stosie, drukuje wszystkie liczby pierwsze i pozostawia stos bez jego danych wejściowych. W przypadku wszystkich nieprawidłowych danych wejściowych spowoduje to wyświetlenie błędu lub nic nie wydrukuje.

Większość kodu to sprawdzanie poprawności danych wejściowych, a następnie sito Eratostenesa. Musiałem tylko obejść ograniczenie wejściowe w 3 miejscach:

• )jest przyrostem w CJam. Potrzebowałem tego raz, ale mogłem go zastąpić ~(uzupełnieniem bitowym), ponieważ i tak później kwadrowałem liczby.
• %jest modulo. Używam 37c~zamiast tego, który najpierw tworzy postać, %a następnie ewaluuje. To sprawia, że ​​kod jest znacznie wolniejszy.
• ;wyskakuje i odrzuca element ze stosu. Muszę to zrobić na końcu. Zamiast tego używam, '<(~który popycha postać <, zmniejsza ją i ewaluuje.

Bash + coreutils, 227 bajtów

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

To było dość trudne. Niektóre rzeczy, na które wpadłem:

• Większość pętli ( whilei until) jest bezużytecznych, ponieważ najbardziej się zbliżają, doneco jest słowem kluczowym powłoki i nie może być wynikiem zmiennego rozszerzenia (chyba że evalzostanie użyte, ale to też nie działa). Jedyną możliwą do użycia pętlą jest for/, inktóra pozwala {/ }zamiast do/ done. for (( ; ; ))również nie nadaje się do użytku.
• =jest obecnie niedostępny, dlatego potrzebujemy innego sposobu przypisywania zmiennych. printf -vjest do tego dobry.
• Wiemy, że p (10000) wynosi 104729, więc dla zewnętrznej pętli dla potencjalnych liczb pierwszych możemy po prostu zapętlić od 2 do 104729 i przerwać, gdy mamy wystarczającą liczbę liczb pierwszych
• jotgeneruje listę potencjalnych czynników w wewnętrznej pętli. Jeśli potencjalny czynnik dzieli potencjalną liczbę pierwszą, to nie jest ona liczbą pierwszą i zaczynamy wcześnie
• Na szczęście breakjest wbudowana powłoka, a nie słowo kluczowe, więc może zostać wygenerowana w wyniku rozszerzenia. dckonwertuje liczbę podstawową 13 na bajteak .
• Aby sprawdzić, czy potencjalny czynnik dzieli potencjalną liczbę pierwszą, nie możemy użyć zwykłych /lub %powłokowych operatorów arytmetycznych. Jest to zlecane operatorowi dcs ~, który wypycha iloraz i resztę na stos.
• -lt - mniej niż - jest jedynym użytecznym operatorem porównywania powłok.
• echonie ma zastosowania dla danych wyjściowych. printfdziała tak długo, jak unikamy%

Właściwe sprawdzenie poprawności danych wejściowych jest trochę uciążliwe. Nic nie zwraca w przypadku nieprawidłowego wejścia.

Wydajność:

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

Haskell, 90 bajtów

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

Jest to anonimowa funkcja, która przyjmuje na nwejściu liczbę całkowitą .

Jak to działa: [p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]](pierwszy przykład jednowierszowych liczb pierwszych na wiki Haskell, ale z elemzastąpioną funkcją) tworzy nieskończoną listę liczb pierwszych. zipz liczbami od 1do, naby utworzyć listę (prime, seq. number)par. Usuń sekw. znowu numer. Wynikiem jest lista liczb pierwszych n.

Rdza, 64897 bajtów

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

(kod został wycięty z powodu limitu znaków, pełne rozwiązanie tutaj )

Następujące funkcje rdzy stają się niedostępne z powodu podstawowego ograniczenia:

• wywołania funkcji, ponieważ wymagają „)”
• regularne wiązania, ponieważ wymagają let (e)
• definicje makr, wymagają one reguł makro! (a, e, m)
• instrukcje match, wymagają dopasowania (a, m) i => (=)
• zmienność, ponieważ zawsze jest wprowadzana za pomocą słowa kluczowego mut (m).
• powrót (e), przerwa (a, e), kontynuacja (e)
• else (e)

Czego możesz technicznie użyć:

• Jeśli. Ale bez tego są one bezużyteczne w kontekście ekspresji, więc są dobre tylko dla efektów ubocznych.
• makra. Standardowe makra, takie jak print! po nich zwykle występuje (), ale w rzeczywistości dozwolone jest użycie {} lub []. Bez tego zadanie byłoby niemożliwe.
• zamknięcia, w najbardziej wąskim tego słowa znaczeniu. Nie możesz ich wywoływać (wymaga ()) ani wiązać (wymaga let), ale możesz zdefiniować jeden nierekurencyjny. Bez tego zadanie oczywiście stałoby się niemożliwe.
• structs.
• dla pętli. Są obiecujące, ponieważ faktycznie umożliwiają zmienne wiązanie i wymagają iteratora, który nadal można zdefiniować za pomocą składni zakresu. Iterator może być nawet wyrażeniem.
• Wbudowane operatory, z wyjątkiem +,% i /. Operatory logiczne zwierające wydają się obiecujące.

Po prostu nie mogłem nic skompletować za pomocą tych narzędzi. Przepraszam. Pozostało tylko pełne pierwsze 10000 liczb pierwszych, oczyszczonych z 5. Przynajmniej możesz go pokroić i mieć prawidłowe rozwiązanie, w najściślejszym możliwym sensie.

Bardzo chciałbym, aby eksperci od nurkowania na tarnecie Turinga (lub na Rust!) Powiedzieli mi, czy mogłem zrobić coś lepszego!

GNU APL, 75 68 67 65 59 56 55 znaków

⎕IOmusi być 1.

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

Wróciłem w tym miesiącu później, zdając sobie sprawę, że mam dodatkową przestrzeń!

Pyth - 12 bajtów

Używa funkcji faktoryzacji liczby pierwszej Pytha, aby sprawdzić, czy liczba # jest liczbą pierwszą. Wykorzystuje !tPTsztuczkę zasugerowaną mi przy mojej odpowiedzi dla liczb pierwszych poniżej miliona problemów.

<f!tPTr2^T6Q

Ponieważ filtr działa tylko dla liczb pierwszych poniżej n, a nie dla pierwszego n, po prostu sprawdziłem odwrotność pi (x) dla 10 000 i otrzymałem 104 000, więc używam liczb pierwszych poniżej 10 under i otrzymuję pierwsze n. To faktycznie nie biegać, więc należy przetestować zastępując ^T6ze ^T3i ograniczyć n do poniżej 1000. Wejście ze standardowego wejścia i wyjścia na standardowe wyjście.

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