Lista liczb pierwszych poniżej miliona

56

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.

Delan Azabani
źródło
12
Nie jest to dokładny duplikat, ale w gruncie rzeczy jest to po prostu test pierwotności, który jest składnikiem wielu istniejących pytań (np. Codegolf.stackexchange.com/questions/113 , codegolf.stackexchange.com/questions/5087 , codegolf.stackexchange. com / pytania / 1977 ). FWIW, jedną z wytycznych, która nie jest wystarczająco przestrzegana (nawet przez osoby, które powinny wiedzieć lepiej) jest wstępne zaproponowanie pytania w meta sandbox meta.codegolf.stackexchange.com/questions/423 w celu krytyki i dyskusji na temat tego, jak można to zrobić poprawione, zanim ludzie zaczną na nie odpowiadać.
Peter Taylor
Ach, tak, martwiłem się, że to pytanie jest zbyt podobne do mnóstwa pytań dotyczących liczb pierwszych, które już istnieją.
Delan Azabani
2
@ GlennRanders-Pehrson Ponieważ 10^6jest jeszcze krótszy;)
14ıʇǝɥʇuʎs
1
Kilka lat temu przesłałem wpis IOCCC, który drukuje liczby pierwsze zawierające tylko 68 znaków w C - niestety zatrzymuje się znacznie poniżej
Computronium
1
@ ɐɔıʇǝɥʇuʎs Co powiesz na 1e6:-D
Tytusa

Odpowiedzi:

33

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
Mr.Wizard
źródło
4
Prime~Array~78498również 17 :)
chyanog,
Byłoby dziewięć bajtów w mthmca, gdyby to miało być wydane.
Michael Stern
To narusza warunek jednej liczby pierwszej na linię wyjściową. Prefiksowanie Print/@i kończenie za pomocą, ;aby zapobiec wyświetlaniu długiej listy Nullpoprawek s, które kosztem 8 dodatkowych znaków.
celtschk
@celtschk Nie wiem, czy tęskniłem, czy lekceważyłem to pięć lat temu.
Mr.Wizard
1
Cóż, zdecydowanie tęskniłem za tym sprzed pięciu lat :-)
celtschk
27

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

xnor
źródło
23

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++);}
ugoren
źródło
Dostałem SEG-FAULTpo wydrukowaniu881
manav mn
7
@Manav, być może skompilowałeś bez optymalizacji. Opiera się na dobrym optymalizatorze, który usunie rekurencję.
ugoren
4
Tak, -O3aby gccrozwiązać problem !!
manav mn
Ta metoda jest szalona. Kocham to.
Todd Lehman
2
Mogę cię doprowadzić do 57 bajtówn=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
Albert Renshaw
22

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)'
MBraedley
źródło
5
Używanie 1e6zamiast 1000000pomaga tutaj.
orion
@orion To by było 11 znaków
Axoren
@Axoren, który nie obejmuje 'końca
Stan Strum
20

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.

saeedn
źródło
Można to ulepszyć do: seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
Delan Azabani
tak, masz rację. Polecenie sed napisałem jako czyste, nie golfowe: P
saeedn
3
seq 1e6|factor|awk '$0=$2*!$3'jest nieco krótszy.
Dennis
1
seq, factor i sed są programami zewnętrznymi, równie dobrze może być c ptam, gdzie c jest dowiązaniem symbolicznym do cat, a p to plik tekstowy z liczbami pierwszymi do miliona ... czy możesz to zrobić z wbudowanymi powłokami?
technozaur
7
@technosaurus seqi już factorcoreutils, więc jest to uzasadnione. sedjest również dość wszechobecny. coreutilsmożna traktować jak wbudowany. Bash bez coreutils jest jak C ++ bez STL.
16

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.

Gareth
źródło
2
Używając elementów enfile ,., zamiast 1 [\\, aby zapisać znak. Usuń niepotrzebne nawias i używać notacji wykładniczej: 1e6.
Omar,
Przyszło mi do ,.i.&.(p:^:_1)1e6głowy : nie krócej (po zastosowaniu sugestii @Omara), ale użycie tego było zbyt interesujące.
kaoD
10

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
Rynant
źródło
9

Rubin 34

require'prime';p Prime.take 78498
Hauleth
źródło
9

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.

Dennis
źródło
4
awk '$0=$2*!$3'jest niesamowicie fajny!
yeti
8

Rubin 50 41

require'mathn'
p (2..1e6).select &:prime?
Cristian Lupascu
źródło
2
Nie ma takiej potrzeby .to_a, jak już zawiera Enumerableselect . Możesz także użyć skrótu do symbolu # to_proc, aby go jeszcze bardziej skrócić: p (2..1e6).select &:prime?(1 nie jest liczbą pierwszą)
Ventero
@Ventero wielkie dzięki! Nie wiedziałem o symbolu # to_proc. Muszę zwracać większą uwagę na skróty oferowane przez Ruby.
Cristian Lupascu
2
Krótsza wersja require'prime';p Prime.take 78498.
Hauleth,
@ ŁukaszNiemier Świetnie! Myślę, że to tak różne, że możesz opublikować to jako osobną odpowiedź.
Cristian Lupascu
Dobre wykorzystanie dobrego starego wiejskiego matematyki
DoctorHeckle 27.04.16
8

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+$'

źródło
2
Wow - nigdy factorwcześniej nie spotkałem , ale jest tam w coreutils!
Cyfrowa trauma
1
Ogol jedną postać: seq 1e6|factor|grep -oP "(?<=: )\d+$"wyglądając perlowo-grepowo
Digital Trauma
@DigitalTrauma jak to działa
1
-Pwłącza wyrażenia regularne w stylu perla. (?<=: )jest dodatnim wyglądem dla ciągu „:”. Zasadniczo mówi to, że „:” musi pojawić się przed tym \d+$, co pasuje , ale tak naprawdę nie jest częścią dopasowania, więc -oopcja daje nam tylko jeden pasujący numer po dwukropku, tj. Podaje tylko liczby, w których występuje tylko jeden czynnik, tj. Liczba pierwsza.
Cyfrowa trauma
@DigitalTrauma dodano
8

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)
dan04
źródło
1
Pierwszy błędnie drukuje 0i 1. Możesz to naprawić, używając zamiast tego range(2,10**6). Ponadto uważam, że ifinstrukcja musi znajdować się w osobnym wierszu niż out, forinaczej wystąpi błąd.
xnor
@xnor: Naprawiono.
dan04
8

Haskell, 51

mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]
pt2121
źródło
Możesz zmienić mapM_na mapM, zwracana wartość nie zostanie wydrukowana, a to jest Code Golf. ;)
Dogbert
dlaczego są dodatkowe spacje po wydrukowaniu i w (> 0)?
dumny haskeller
dobry chwyt! dzięki
pt2121
Możesz zastąpić 999999 10 ^ 6. I proszę zaktualizować liczbę bajtów - 63 prawdopodobnie nie może mieć racji.
user2845840,
@ user2845840 ok dzięki. dobry pomysł!
pt2121
8

APL, 15

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

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

TwiNight
źródło
W jaki sposób? Czy możesz podać biurokrację?
Rasmus Damgaard Nielsen
Potrzebujesz znaku z przodu, aby utworzyć jeden numer na linię, i nie potrzebujesz ,.
Adám
@RasmusDamgaardNielsen to pierwsze liczby całkowite. 1↓upuszcza pierwszy. p←przypisuje do p. p∘.×ptworzy tabliczkę mnożenia. p~usuwa z p wszystko, co jest po prawej stronie. ( ,nie jest potrzebny, wrzuca tabelę w listę.)
Adám
8

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

Gowtham
źródło
2
zainspirowało mnie do napisania wersji perl6. również 1000000można napisać10**6
pabo
1
Można również napisać 1000000 1E6
tłum
Zaktualizowałem moją odpowiedź. Dzięki @mob
Gowtham
Zawsze był moim ulubionym wyrażeniem regularnym, ale musisz pamiętać, że po spektakularnym osiągnięciu większej liczby nie udaje mu się to spektakularnie - z uwagi na fakt, że zamienia on wielkie liczby na jednoargumentowe. Ten wyrażenie regularne może nie działać w celu znalezienia liczb pierwszych w setkach tysięcy i później, w zależności od konfiguracji języka (i komputera).
Codefun64
7

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.

gggg
źródło
7

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
.ıʇǝɥʇuʎs
źródło
1
... The output format should be one number per line of output.Dlatego moja odpowiedź zaczyna się od 1[\ .
Gareth
6

gs2, 5 bajtów

Zakodowane w CP437:

∟)◄lT

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

Lynn
źródło
5

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)
Dennis
źródło
Czy „wolne” sito to tylko sito Eratostenesa?
dorukayhan
Oba są. Wersja powolna jest po prostu okropną implementacją.
Dennis
5

NARS2000 APL, 7 znaków

⍸0π⍳1e6
Ul
źródło
3
Witamy w Programowaniu Puzzle i Code Golf!
Dennis
4

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=},`
Cristian Lupascu
źródło
Możesz uratować postać, zastępując \;*. (Możesz również uzyskać znacznie szybsze obliczanie liczby obecnych postaci, znajdując pierwszy dzielnik zamiast wszystkich:10 6?,2>{.),2>{1$\%!}?=},`
Peter Taylor
@PeterTaylor Dzięki, dzięki mnożeniu jest bardzo fajna sztuczka.
Cristian Lupascu
Jest jeszcze jedna oszczędność ze zmienną char zamienić .,z :x,i \.@z x\ (spacje z powodu ucieczki problemy z MD w komentarzach) i zdjąć *.
Peter Taylor
@PeterTaylor dobry, dziękuję! Zmodyfikowałem swój kod.
Cristian Lupascu,
4

CJam - 11

1e6,{mp},N*

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

aditsu
źródło
1
Czy CJam nie jest nowszy od tego pytania?
Peter Taylor
@PeterTaylor o tak, tak jest
aditsu
4

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

                                                      (n - 1)!  = -1 (mod n)

!     # 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ź .

Dennis
źródło
3

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.

Gareth
źródło
1
możesz go łatwo skrócić: main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}lub jakiś taki pomysł (skoro go nie skompilowałem)
Ali1S232
Jak na ipewno będzie 0? Myślę, że jeśli podasz jakiś argument, zawiedzie. Myślę też, że jwystąpi jakiś błąd typu. Nie jestem pewien b.
Erik the Outgolfer,
3

Mathematica 25

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

Prime@Range@PrimePi[10^6]
DavidC
źródło
3

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.

rationalis
źródło
3

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.

plannapus
źródło
Pierwsza liczba wygenerowana przez ten kod to 1, ale 1 nie jest liczbą pierwszą.
Sven Hohenstein,
@SvenHohenstein Dzięki, poprawione.
plannapus
3

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.

Kevin Cox
źródło
+1 Ta odpowiedź jest naprawdę diabelska. Niezupełnie obliczony wynik (pozwala zaoszczędzić sporo znaków) i znacznie trudniejszy do obliczenia :) Jest to prawdopodobnie także przykład, który sprawia, że ​​zoptymalizowane factordziałanie jest znacznie gorsze niż podstawowy algorytm podziału próby.
orion
3

C #, 70

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

Długo się tu nie zobaczycie ...

It'sNotALie.
źródło
Jest kilka powodów, dla których jest to źle. (1) Nie można pośrednio przekonwertować z a double 1e6na int, ale intjest to wymagane przez Range. (2) Wewnętrzne Rangemusi przyjmować co najwyżej n-2warunki, w przeciwnym razie przetestujesz, n % nco jest wyraźnie 0. (3) Piszesz, x%nkiedy chcesz n%x. Rozwiązując te problemy, coś takiego będzie działać: Enumerable.Range(2,999999).Where(n=>Enumerable.Range(2,n-2).All(x=>n%x!=0))Jednak nadal nie wyświetla to liczb; wymagano jednego na linię.
Jeppe Stig Nielsen