To jest moje pierwsze pytanie w golfa i bardzo proste, dlatego z góry przepraszam, jeśli mogłem złamać jakieś wytyczne społeczności.

Zadanie polega na wydrukowaniu w porządku rosnącym wszystkich liczb pierwszych mniejszych niż milion. Format wyjściowy powinien wynosić jedną liczbę na linię wyjściową.

Celem, podobnie jak większości zgłoszeń do gry w golfa, jest zminimalizowanie rozmiaru kodu. Optymalizacja pod kątem czasu działania jest również bonusem, ale jest celem drugorzędnym.

Mathematica , 17 24

Dla porównania:

Prime@Range@78498

Jak zauważono w komentarzu, nie podałem jednej liczby pierwszej na linię; korekta:

Column@Prime@Range@78498

Python 3, 46 bajtów

k=P=1
while k<1e6:P%k and print(k);P*=k*k;k+=1

Zanim pętla osiągnie testowanie k, iteracyjnie obliczyła czynnik kwadratowy P=(k-1)!^2. Jeśli kjest liczbą pierwszą, to nie pojawia się w produkcie 1 * 2 * ... * (k-1), więc nie jest to czynnikiem P. Ale jeśli jest złożony, wszystkie jego czynniki pierwsze są mniejsze, a więc w produkcie. Kwadratowanie jest właściwie potrzebne tylko po to, by powstrzymać się k=4od fałszywego nazywania liczbą pierwszą.

Mocniej wynika z twierdzenia Wilsona, że gdy liczba kpierwsza jest P%krówna 1. Chociaż potrzebujemy tylko, aby nie była tutaj zerowa, ogólnie P%kjest użyteczna, ponieważ jest zmienną wskaźnikową określającą, czy kjest liczbą pierwszą.

C, 61 znaków

Prawie dokładnie taki sam jak ten (pytanie jest prawie dokładnie takie samo).

n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}

MATLAB (16) (12)

Niestety dane wyjściowe w jednym wierszu:

primes(1000000)

ale rozwiązuje to prosta transpozycja macierzy:

primes(1000000)'

i mogę wyciąć niektóre znaki za pomocą notacji wykładniczej (zgodnie z sugestiami w komentarzach):

primes(1e6)'

Bash (37 znaków)

seq 2 1e6|factor|sed 's/.*: //g;/ /d'

(60 znaków)

seq 2 1000000|factor|sed -e 's/[0-9]*: //g' -e '/^.* .*$/ d'

na moim komputerze (procesor 2,0 GHz, 2 GB RAM) trwa 14 sekund.

J, 21 znaków

1[\p:i.(_1 p:1000000)

które można skrócić

1[\p:i.78498

jeśli wiesz, ile liczb pierwszych jest poniżej 1000000.

PowerShell, 47 44 bajtów

Bardzo powoli, ale najkrótszy, jaki mogłem wymyślić.

$p=2..1e6;$p|?{$n=$_;!($p-lt$_|?{!($n%$_)})}

PowerShell, 123 bajty

To jest znacznie szybsze; daleki od optymalnego, ale dobry kompromis między wydajnością a zwięzłością.

 $p=2..1e6;$n=0
 while(1){$p=@($p[0..$n]|?{$_})+($p[($n+1)..($p.count-1)]|?{$_%$p[$n]});$n++;if($n-ge($p.count-1)){break}}
 $p

Rubin 34

require'prime';p Prime.take 78498

Bash, 30 bajtów

Ponieważ saeedn nie zareaguje na moją sugestię - która jest zarówno krótsza, jak i szybsza niż jego podejście - pomyślałem, że opublikuję własną odpowiedź:

seq 1e6|factor|awk '$0=$2*!$3'

Jak to działa

seq 1e6

wyświetla wszystkie liczby całkowite dodatnie do 1 000 000.

factor

uwzględnia je jeden po drugim. Dla pierwszych dziesięciu wynik jest następujący:

1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5

Wreszcie,

awk '$0=$2*!$3'

zmienia całą linię ( $0) na iloczyn drugiego pola (pierwszego czynnika pierwszego) i logicznej negacji trzeciego pola ( 1jeśli jest to jeden czynnik pierwszy lub mniej, w 0przeciwnym razie).

Zastępuje to wiersze odpowiadające liczbom podstawowym samą liczbą, a wszystkie inne wiersze zerami. Ponieważ awk drukuje tylko prawdziwe wartości, drukowana będzie tylko liczba pierwsza.

Rubin 50 41

require'mathn'
p (2..1e6).select &:prime?

Bash, 37 lat

Zagram więcej, jeśli mogę ...

Większość z nich próbuje przeanalizować factorniewygodny format wyjściowy.

seq 1e6|factor|grep -oP "(?<=: )\d+$"

Wykonanie na moim komputerze zajmuje około 5,7 sekundy.

(Zdarzyło się, że mój post jako pierwszy wszedł na drugą stronę odpowiedzi, więc nikt go nie zobaczy ...)

Stare rozwiązanie

Jest to dłuższe i wolniejsze (zajmuje 10 sekund).

seq 1e6|factor|egrep ':.\S+$'|grep -oE '\S+$'

Python 3.x: 66 znaków

for k in range(2,10**6):
 if all(k%f for f in range(2,k)):print(k)

Bardziej wydajne rozwiązanie: 87 znaków

Na podstawie sita Eratostenesa.

p=[];z=range(2,10**6)
while z:f=z[0];p+=[f];z=[k for k in z if k%f]
for k in p:print(k)

Haskell, 51

mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]

APL, 15

p~,p∘.×p←1↓⍳1e6

Mój tłumacz napotkał problemy z pamięcią, ale działa teoretycznie.

Perl, 49 bajtów

Wyrażenie regularne kung fu :)

for(1..1E6){(1x$_)=~/^(11+?)\1+$/ or print"$_\n"}

Wersja bez golfa:

for(1 .. 1_000_000) { 
    (1x$_) =~ /^(11+?)\1+$/ or print "$_\n";
}

Nie poczyniłem nawet 10% postępu, gdy piszę ten post!

Źródło wyrażenia regularnego: http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

Julia, 11 lat

primes(10^6)

Wygląda na to, że wbudowane opinie są coraz bardziej popularne, a do dłuższej odpowiedzi potrzebowałem więcej słów.

J (15 lub 9)

Nie mogę uwierzyć, że ten beat Mathematica (nawet jeśli jest to singiel o 2 znaki)

a#~1 p:a=:i.1e6

Lub:

p:i.78498

gs2, 5 bajtów

Zakodowane w CP437:

∟)◄lT

1C 29popycha milion, 11 6Cjest liczbą pierwszą poniżej, 54pokazuje linie.

GolfScript, 22/20 (20/19) bajtów

n(6?,:|2>{(.p|%-.}do:n

Kosztem prędkości kod może zostać skrócony o dwa bajty:

n(6?,:|2>.{|%2>-}/n*

Jeśli format wyjściowy określony w edytowanym pytaniu zostanie pominięty (co robi wiele istniejących odpowiedzi), dwa bajty można zapisać w szybkiej wersji, a jeden w wolniejszym:

n(6?,:|2>{(.p|%-.}do
n(6?,:|2>.{|%2>-}/`

Spowoduje to wydrukowanie dodatkowego LF po liczbach pierwszych dla wersji szybkiej i wydrukuje liczby pierwsze jako tablicę dla wersji wolnej.

Jak to działa

Obie wersje są implementacjami sita Eratostenesa .

Szybka wersja wykonuje następujące czynności:

1. Ustaw A = [ 2 3 4 … 999,999 ]i | = [ 0 1 2 … 999,999 ].

2. Ustaw N = A[0]i wydrukuj N.

3. Zebrać wszystkie n-ty element z |w C. Są to wielokrotności N.

4. Set A = A - C.

5. Jeśli Anie jest pusty, wróć do 2.

n(6?   # Push "\n".pop() ** 6 = 1,000,000.
,:|    # Push | = [ 0 1 2 … 999,999 ].
,2>    # Push A = [ 2 3 4 … 999,999 ].
{      #
  (    # Unshift the first element (“N”) of “A”.
  .p   # Print “N”.
  |%   # Collect every N-th element from “A” into a new array, starting with the first.
  -    # Take the set difference of “A” and the array from above.
  .    # Duplicate the set difference.
}do    # If the set difference is non-empty, repeat.
:n     # Store the empty string in “n”, so no final LF will get printed.

Wersja powolna działa w podobny sposób, ale zamiast sukcesywnego usuwania wielokrotności minimum „A” (co zawsze jest liczbą pierwszą), usuwa wielokrotności wszystkich liczb całkowitych dodatnich poniżej 1 000 000.

Konkurencyjność

W przypadku braku wbudowanych funkcji matematycznych do faktoryzacji lub sprawdzenia pierwszeństwa, wszystkie rozwiązania GolfScript będą albo bardzo duże, albo bardzo nieefektywne.

Choć wciąż daleko mi do wydajności, wydaje mi się, że osiągnąłem przyzwoity stosunek prędkości do wielkości. W chwili jego przedstawienia takie podejście wydaje się być najkrótsze z tych, które nie wykorzystują żadnego z wyżej wymienionych wbudowanych elementów. Mówię, wydaje się, ponieważ nie mam pojęcia, jak działają niektóre odpowiedzi ...

Dokonałem analizy porównawczej wszystkich czterech przesłanych rozwiązań GolfScript: w0lf (podział próbny), mojej drugiej odpowiedzi (twierdzenie Wilsona) i dwóch z tej odpowiedzi. Oto wyniki:

Bound     | Trial division     | Sieve (slow)       | Wilson's theorem | Sieve (fast)
----------+--------------------+--------------------+------------------+----------------
1,000     | 2.47 s             | 0.06 s             | 0.03 s           | 0.03 s
10,000    | 246.06 s (4.1 m)   | 1.49 s             | 0.38 s           | 0.14 s
20,000    | 1006.83 s (16.8 m) | 5.22 s             | 1.41 s           | 0.38 s
100,000   | ~ 7 h (estimated)  | 104.65 (1.7 m)     | 35.20 s          | 5.82 s
1,000,000 | ~ 29 d (estimated) | 111136.97s (3.1 h) | 3695.92 s (1 h)  | 418.24 s (7 m)

NARS2000 APL, 7 znaków

⍸0π⍳1e6

Golfscript 26 25 24

Edytuj (zapisałem jeszcze jeden znak dzięki Peterowi Taylorowi):

10 6?,{:x,{)x\%!},,2=},`

Stary kod:

10 6?,{.,{)\.@%!},,2=*},`

Ten kod ma tylko wartość teoretyczną, ponieważ jest niewiarygodnie wolny i nieefektywny. Myślę, że uruchomienie może potrwać kilka godzin.

Jeśli chcesz to przetestować, spróbuj na przykład tylko liczb pierwszych do 100:

10 2?,{:x,{)x\%!},,2=},`

CJam - 11

1e6,{mp},N*

1e6,- tablica 0 ... 999999
{mp},- wybierz liczby pierwsze
N*- połącz z nowymi liniami

GolfScript, 25 (24) bajtów

!10 6?,2>{.(@*.)@%!},n*\;

Jeśli format wyjściowy określony w edytowanym pytaniu zostanie pominięty, można zapisać jeden bajt:

!10 6?,2>{.(@*.)@%!},`\;

Spowoduje to wydrukowanie liczb pierwszych jako tablicy (jak robi to wiele innych rozwiązań) zamiast jednej w linii.

Jak to działa

Ogólna idea polega na użyciu twierdzenia Wilsona , które stwierdza, że n > 1 jest liczbą pierwszą wtedy i tylko wtedy

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

Benchmarki

Szybszy niż podział próbny, ale wolniejszy niż sito Eratostenesa. Zobacz moją drugą odpowiedź .

Java, 110 bajtów

void x(){for(int i=1;i++<1e6;)System.out.print(new String(new char[i]).matches(".?|(..+?)\\1+")?"":(i+"\n"));}

Wykorzystanie podziału jednoargumentowego przez wyrażenie regularne jako testu pierwotności.

C, 91 88 85 82 81 80 76 72 znaków

main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}

Algorytm jest strasznie nieefektywny, ale ponieważ uprawiamy golfa kodu, nie powinno to mieć znaczenia.

Mathematica 25

Zakładając, że nie znasz liczby liczb pierwszych mniejszych niż 10 ^ 6:

Prime@Range@PrimePi[10^6]

J, 16 znaków

1]\(#~1&p:)i.1e6

Bez wymogu formatu wyjściowego można to zmniejszyć do 13 znaków:

(#~1&p:)i.1e6

1]\ po prostu bierze tablicę liczb pierwszych 1, zamienia ją w tablicę liczb 2 i umieszcza każdą liczbę pierwszą w osobnym rzędzie - tak więc domyślny format wyjściowy interpretera zamienia listę jednej linii w jedną liczbę pierwszą w linii.

(#~ f) yjest w zasadzie filter, gdzie fzwraca wartość logiczną dla każdego elementu w y. i.1e6jest zakresem liczb całkowitych [0,1000000) i 1&p:jest funkcją logiczną, która zwraca 1 dla liczb pierwszych.

R, 45 43 znaków

for(i in 2:1e6)if(sum(!i%%2:i)<2)cat(i," ")

Dla każdej liczby x od 2 do 1e6 po prostu ją wypisz, jeśli liczba x mod 2 do x, które są równe 0, jest mniejsza niż 2.

Bash (433643)

Moja (niezbyt sprytna) próba użycia współczynnika do uwzględnienia produktu.

factor ${PRODUCT}

Niestety przy dużych liczbach produkt jest oczywiście ogromny. Uruchomienie zajęło również ponad 12 godzin. Postanowiłem go jednak opublikować, ponieważ uważałem, że jest wyjątkowy.

Oto pełny kod.

Gdyby było liczbą pierwszą poniżej szóstej, byłoby rozsądne.

  factor 30

No cóż, próbowałem.

C #, 70

Enumerable.Range(1,1e6).Where(n=>Enumerable.Range(2,n).All(x=>x%n!=0))

Długo się tu nie zobaczycie ...