Zasady są proste:

• Pierwszych n liczb pierwszych (nie liczb pierwszych poniżej n ), należy wydrukować na standardowe wyjście oddzielone znakami nowej linii (liczby pierwsze należy wygenerować w kodzie)
• liczby pierwsze nie mogą być generowane przez wbudowaną funkcję lub przez bibliotekę , tj. użycie wbudowanej funkcji bibliotecznej, takiej jak: prime = get_nth_prime (n), is_a_prime (liczba) lub factorlist = lista_wszystkie_faktory (liczba) nie będzie bardzo kreatywna.

• Punktacja - Powiedzmy, że definiujemy wynik = f ([liczba znaków w kodzie]), O ( f (n)) jest złożonością twojego algorytmu, gdzie n jest liczbą liczb pierwszych, które znajdzie. Na przykład, jeśli masz kod 300 znaków ze złożonością O (n ^ 2), wynik to 300 ^ 2 = 90000 , dla 300 znaków z O (n * ln (n)) wynik wynosi 300 * 5,7 = 1711.13 ( dla uproszczenia załóżmy, że wszystkie logi są logami naturalnymi)

• Użyj dowolnego języka programowania, wygrywa najniższy wynik

Edycja: Problem został zmieniony z znajdowania „pierwszych 1000000 liczb pierwszych” na „pierwsze n liczb pierwszych” z powodu niejasności co do tego, czym jest „n” w O (f (n)), n oznacza liczbę znalezionych liczb pierwszych (znalezienie liczb pierwszych jest problem tutaj, a więc złożoność problemu zależy od liczby znalezionych liczb pierwszych)

Uwaga: aby wyjaśnić pewne nieporozumienia dotyczące złożoności, jeśli „n” oznacza liczbę liczb pierwszych, a „N” jest n-tą znalezioną liczbą pierwszą, złożoność pod względem n jest, a N nie jest równoważna, tj. O (f (n))! = O (f (N)) as, f (N)! = Stała * f (n) i N! = Stała * n, ponieważ wiemy, że n-ta funkcja pierwsza nie jest liniowa, chociaż odkąd znaleźliśmy „n” złożoność liczb pierwszych powinna być łatwo wyrażalna w kategoriach „n”.

Jak zauważył Kibbee, możesz odwiedzić tę stronę, aby zweryfikować swoje rozwiązania ( tutaj jest stara lista dokumentów Google)

Uwzględnij je w swoim rozwiązaniu -

• jaki stopień złożoności ma Twój program (uwzględnij podstawową analizę, jeśli nie banalną)

• długość znaku w kodzie

• końcowy obliczony wynik

To jest moje pierwsze pytanie CodeGolf, więc jeśli w powyższych zasadach występuje błąd lub luka, proszę je wskazać.

Python (129 znaków, O (n * log log n), wynik 203,948)

Powiedziałbym, że Sito Eratostenesa jest właściwą drogą. Bardzo prosty i stosunkowo szybki.

N=15485864
a=[1]*N
x=xrange
for i in x(2,3936):
 if a[i]:
  for j in x(i*i,N,i):a[j]=0
print [i for i in x(len(a))if a[i]==1][2:]

Ulepszony kod wcześniej.

Python ( 191 156 152 znaków, O (n * log log n) (?), Wynik 252,620 (?))

Nie mogę w ogóle obliczyć złożoności, to najlepsze przybliżenie, jakie mogę podać.

from math import log as l
n=input()
N=n*int(l(n)+l(l(n)))
a=range(2,N)
for i in range(int(n**.5)+1):
 a=filter(lambda x:x%a[i] or x==a[i],a)
print a[:n]

n*int(l(n)+l(l(n)))jest górną granicą trzeciej liczby npierwszej.

Haskell, n ^ 1,1 empiryczna stopa wzrostu, 89 znaków, wynik 139 (?)

Poniższe działa w wierszu poleceń GHCi, gdy biblioteka ogólna, której używa, została wcześniej załadowana. Drukuj n-tą pierwszą, opartą na 1:

let s=3:minus[5,7..](unionAll[[p*p,p*p+2*p..]|p<-s])in getLine>>=(print.((0:2:s)!!).read)

To jest nieograniczone sito Eratostenesa, wykorzystujące bibliotekę ogólnego użytku do uporządkowanych list. Empiryczna złożoność między 100 000 a 200 000 liczb pierwszych O(n^1.1). Pasuje do O(n*log(n)*log(log n)).

O oszacowaniu złożoności

Zmierzyłem czas pracy dla liczb pierwszych 100 000 i 200 000, a następnie obliczyłem logBase 2 (t2/t1), który wyprodukował n^1.09. Definiowanie g n = n*log n*log(log n), obliczanie logBase 2 (g 200000 / g 100000)daje n^1.12.

Ale 89**1.1 = 139mimo to g(89) = 600. --- (?)

Wydaje się, że do oceny należy zastosować szacowaną stopę wzrostu zamiast samej funkcji złożoności. Na przykład, g2 n = n*((log n)**2)*log(log n)jest dużo lepszy niż n**1.5, ale z 100 znaków SCORE dwa produkty z 3239i 1000, odpowiednio. To nie może być prawda. Szacowanie dla zasięgu 200k / 100k daje logBase 2 (g2 200000 / g2 100000) = 1.2i tym samym wynik 100**1.2 = 251.

Nie próbuję też drukować wszystkich liczb pierwszych, tylko n-ta liczba pierwsza.

Bez importu, 240 znaków. n ^ 1,15 empiryczna stopa wzrostu, wynik 546.

main=getLine>>=(print.s.read)
s n=let s=3:g 5(a[[p*p,p*p+2*p..]|p<-s])in(0:2:s)!!n
a((x:s):t)=x:u s(a$p t)
p((x:s):r:t)=(x:u s r):p t
g k s@(x:t)|k<x=k:g(k+2)s|True=g(k+2)t
u a@(x:r)b@(y:t)=case(compare x y)of LT->x:u r b;EQ->x:u r t;GT->y:u a t

Haskell, 72 89 znaków, O (n ^ 2), wynik 7921

Najwyższy wynik na liczbę znaków wygrywa, prawda? Zmodyfikowany dla pierwszego N. Również najwyraźniej nie mogę użyć kalkulatora, więc mój wynik nie jest tak fatalnie zły, jak myślałem. (używając złożoności do podstawowego podziału próby, jak podano w poniższym źródle).

Zgodnie z Willem Nessem poniżej nie jest pełnym programem Haskell (w rzeczywistości opiera się na REPL). Poniżej znajduje się bardziej kompletny program z pseudo-sitem (import faktycznie oszczędza znak, ale nie lubię importu w kodzie golfowym).

main=getLine>>= \x->print.take(read x).(let s(x:y)=x:s(filter((>0).(`mod`x))y)in s)$[2..]

Ta wersja jest bez wątpienia (n ^ 2). Algorytm jest po prostu golfową wersją naiwnego `` sita '', jak widać tutaj Old ghci 1 liner

getLine>>= \x->print.take(read x)$Data.List.nubBy(\x y->x`mod`y==0)[2..]

Pozostawiając starą, zdradzającą odpowiedź, ponieważ biblioteka, do której prowadzi łącze, jest całkiem niezła.

print$take(10^6)Data.Numbers.Primes.primes

Zobacz tutaj implementację i linki do złożoności czasu. Niestety koła mają czas wyszukiwania log (n), co spowalnia nas o czynnik.

C #, 447 Postaci, bajty 452, wynik?

using System;namespace PrimeNumbers{class C{static void GN(ulong n){ulong primes=0;for (ulong i=0;i<(n*3);i++){if(IP(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}static bool IP(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}static void Main(string[] args){ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GN(i);}}}}

skrypt, wariant, 381 znaków, 385 bajtów, wynik?

using System;static void GetN(ulong n){ulong primes=0;for (ulong i=0;i<(n*500);i++){if(IsPrime(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}public static bool IsPrime(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GetN(i);}

Jeśli zainstalujesz skrypty, możesz je uruchomić.

PS Napisałem to w Vimie :D

GolfScript (45 znaków, wynik deklarowany ~ 7708)

~[]2{..3${1$\%!}?={.@\+\}{;}if)1$,3$<}do;\;n*

To robi prosty podział próbny według liczb pierwszych. Jeśli w pobliżu krawędzi Ruby (tj. Używając 1.9.3.0) arytmetyka wykorzystuje mnożenie Toom-Cook 3, więc podział próbny wynosi O (n ^ 1,465), a całkowity koszt podziałów wynosi O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)†. Jednak w GolfScript dodanie elementu do tablicy wymaga skopiowania tablicy. Zoptymalizowałem to, aby skopiować listę liczb pierwszych tylko wtedy, gdy znajdzie nową nliczbę pierwszą, więc łącznie tylko razy. Każda operacja kopiowania ma O(n)wielkość O(ln(n ln n)) = O(ln n)†, co daje O(n^2 ln n).

I właśnie dlatego, chłopcy i dziewczęta, GolfScript jest używany raczej do gry w golfa niż do poważnego programowania.

† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). Powinienem to zauważyć, zanim skomentuję różne posty ...

To takie proste, nawet mój edytor tekstu może to zrobić!

Vim: 143 naciśnięcia klawiszy (115 akcji): O (n ^ 2 * log (n)): Wynik: 101485.21

Uległość:

qpqqdqA^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddmpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p

Dane wejściowe: N powinno znajdować się w pierwszym wierszu pustego dokumentu. Po zakończeniu każda liczba pierwsza od 2 do N będzie oddzielną linią.

Uruchamianie poleceń:

Po pierwsze, zauważ, że wszelkie polecenia z karetką przed nimi oznaczają, że musisz przytrzymać Ctrl i wpisać następną literę (np. ^ V to Ctrl-vi ^ R to Ctrl-r).

Spowoduje to zastąpienie wszystkiego w rejestrach @a, @b, @d i @p.

Ponieważ używa qpoleceń, nie można go po prostu umieścić w makrze. Oto jednak kilka wskazówek dotyczących jego uruchamiania.

• qpqqdq po prostu kasuje rejestry
• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddutworzy listę liczb od 2 do N + 1. Jest to przerwa między dwiema głównymi częściami, więc kiedy to zrobisz, nie będziesz musiał tego robić ponownie
• mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@pmusi być wpisany za jednym razem. Staraj się unikać cofania, ponieważ może to coś popsuć.
  • Jeśli popełnisz błąd, wpisz, qdqqpqa następnie spróbuj ponownie użyć tego wiersza.

W przypadku dużych N jest to bardzo wolne. Uruchomienie N = 5000 zajęło około 27 minut; uważaj się za ostrzeżonego.

Algorytm:

Wykorzystuje podstawowy algorytm rekurencyjny do znajdowania liczb pierwszych. Biorąc pod uwagę listę wszystkich liczb pierwszych od 1 do A, A + 1 jest liczbą pierwszą, jeśli nie jest podzielna przez żadną z liczb na liście liczb pierwszych. Zacznij od A = 2 i dodaj liczby pierwsze do listy, gdy zostaną znalezione. Po N rekurencjach lista będzie zawierać wszystkie liczby pierwsze do N.

Złożoność

Algorytm ten ma złożoność O (nN), gdzie N jest liczbą wejściową, a n jest liczbą liczb pierwszych do N. Każda rekurencja bada n liczb i wykonuje się N rekurencji, dając O (nN).

Jednak N ~ n * log (n), co daje ostateczną złożoność jako O (n ² * log (n)) ( https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number )

Wyjaśnienie

Nie jest łatwo rozpoznać przepływ programu na podstawie poleceń vim, więc przepisałem go w Pythonie, wykonując ten sam przepływ. Podobnie jak kod Vima, kod python nie będzie wyświetlany, gdy osiągnie koniec. Python nie lubi zbyt dużej rekurencji; jeśli spróbujesz tego kodu z N> 150, osiągnie maksymalną głębokość rekurencji

N = 20
primes = range(2, N+1)

# Python needs these defined.
mark_p = b = a = -1

# Check new number for factors. 
# This macro could be wrapped up in @d, but it saves space to leave it separate.
def p():
    global mark_d, mark_p, primes, a
    mark_d = 0
    print(primes)
    a = primes[mark_p]
    d()      

# Checks factor and determine what to do next
def d():
    global mark_d, mark_p, a, b, primes
    b = primes[mark_d]
    if(a == b): # Number is prime, check the next number
        mark_p += 1
        p()
    else:
        if(a%b == 0): # Number is not prime, delete it and check next number
            del(primes[mark_p])
            p()
        else: # Number might be prime, try next possible factor
            mark_d += 1
            d()

mark_p = 0 #Start at first number         
p()

Teraz, aby rozbić faktyczne naciśnięcia klawiszy!

• qpqqdqCzyści rejestry @d i @p. Zapewni to, że nic nie uruchomi się podczas konfigurowania tych rekurencyjnych makr.

• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddZamienia dane wejściowe na listę liczb od 2 do N + 1. Wpis N + 1 jest usuwany jako efekt uboczny konfiguracji makra @d.

  • W szczególności zapisuje makro, które zwiększa liczbę, a następnie kopiuje je w następnym wierszu, a następnie zapisuje 1 i wykonuje to makro N razy.

• mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qzapisuje makro @d, które implementuje powyższą funkcję d (). Instrukcje „If” są interesujące do wdrożenia w Vimie. Korzystając z operatora wyszukiwania *, możesz wybrać określoną ścieżkę, którą chcesz podążać. Dalej łamiemy polecenie

  • mpqdUstaw tutaj znak p i rozpocznij rejestrowanie makra @d. Znak p musi być ustawiony, aby istniał znany punkt, do którego można przejść podczas wykonywania
  • o^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc> Zapisuje tekst instrukcji if / else
  • 0*w*wyiWdd@0 faktycznie wykonuje instrukcję if.
  • Przed wykonaniem tego polecenia linia będzie zawierać @a @b 0 0 `pj@p @a 0 (@a%@b) `pdd@p 0 `dj@d
  • 0 przesuwa kursor na początek linii

  • *w*w Przesuwa kursor do kodu, aby wykonać następny

    1. if @a == @b, to znaczy `pj@p, który przechodzi do następnego numeru dla @a i uruchamia na nim @p.
    2. jeśli @a! = @b i @ a% @ b == 0, to znaczy `pdd@p, że usuwa bieżący numer @a, a następnie uruchamia @p na następnym.
    3. jeśli @a! = @b i @ a %% b! = 0, to znaczy `dj@dsprawdza następną liczbę dla @b, aby sprawdzić, czy jest to współczynnik @a

  • yiWdd@0 wciąga polecenie do rejestru 0, usuwa wiersz i wykonuje polecenie

  • q kończy nagrywanie makra @d

• Gdy jest to pierwsze uruchomienie, `pdd@ppolecenie jest uruchamiane, usuwając linię N + 1.

• qpmp"aywgg@dq zapisuje makro @p, które zapisuje liczbę pod kursorem, następnie przechodzi do pierwszego wpisu i uruchamia na nim @d.

• gg@p faktycznie wykonuje @p, aby iterować cały plik.

QBASIC, 98 znaków, Złożoność N Sqrt (N), wynik 970

I=1
A:I=I+2
FOR J=2 TO I^.5
    IF I MOD J=0 THEN GOTO A
NEXT
?I
K=K+1
IF K=1e6 THEN GOTO B
GOTO A
B:

Scala 263 znaków

Zaktualizowano w celu dopasowania do nowych wymagań. 25% kodu dotyczy znalezienia rozsądnej górnej granicy do obliczenia liczb pierwszych poniżej.

object P extends App{
def c(M:Int)={
val p=collection.mutable.BitSet(M+1)
p(2)=true
(3 to M+1 by 2).map(p(_)=true)
for(i<-p){
var j=2*i;
while(j<M){
if(p(j))p(j)=false
j+=i}
}
p
}
val i=args(0).toInt
println(c(((math.log(i)*i*1.3)toInt)).take(i).mkString("\n"))
}

Ja też mam sito.

Oto test empiryczny kosztów obliczeniowych niepoddany analizie:

object PrimesTo extends App{
    var cnt=0
    def c(M:Int)={
        val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
        for (i <- List.range (3, M, 2)
            if (p (i))) {
                var j=2*i;
                while (j < M) {
                    cnt+=1
                    if (p (j)) 
                        p(j)=false
                    j+=i}
            }
        (1 to M).filter (x => p (x))
    }
    val i = args(0).toInt
    /*
        To get the number x with i primes below, it is nearly ln(x)*x. For small numbers 
        we need a correction factor 1.13, and to avoid a bigger factor for very small 
        numbers we add 666 as an upper bound.
    */
    val x = (math.log(i)*i*1.13).toInt+666
    println (c(x).take (i).mkString("\n"))
    System.err.println (x + "\tcount: " + cnt)
}
for n in {1..5} ; do i=$((10**$n)); scala -J-Xmx768M P $i ; done 

prowadzi do następujących liczb:

List (960, 1766, 15127, 217099, 2988966)

Nie jestem pewien, jak obliczyć wynik. Czy warto napisać jeszcze 5 znaków?

scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.13).toInt+666) 
res42: List[Int] = List(672, 756, 1638, 10545, 100045, 1000419, 10068909, 101346800, 1019549994)

scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.3)toInt) 
res43: List[Int] = List(7, 104, 1119, 11365, 114329, 1150158, 11582935, 116592898, 1172932855)

Dla większego n zmniejsza obliczenia o około 16% w tym zakresie, ale czy w przypadku formuły punktacji nie bierzemy pod uwagę stałych czynników?

nowe uwagi Big-O:

Aby znaleźć 1 000, 10 000, 100 000 liczb pierwszych i tak dalej, używam wzoru o gęstości liczb pierwszych x => (math.log (x) * x * 1.3, który określa zewnętrzną pętlę, z której korzystam.

Tak więc dla wartości i w 1 do 6 => NPrimes (10 ^ i) działa 9399, 133768 ... razy pętla zewnętrzna.

Znalazłem tę funkcję O iteracyjnie z pomocą komentarza Petera Taylora, który zasugerował znacznie wyższą wartość potęgowania, zamiast 1,01 zasugerował 1,5:

def O(n:Int) = (math.pow((n * math.log (n)), 1.01)).toLong

O: (n: Int) Long

val ns = List(10, 100, 1000, 10000, 100000, 1000*1000).map(x=>(math.log(x)*x*1.3)toInt).map(O) 

ns: List [Long] = List (102, 4152, 91532, 1612894, 25192460, 364664351)

 That's the list of upper values, to find primes below (since my algorithm has to know this value before it has to estimate it), send through the O-function, to find similar quotients for moving from 100 to 1000 to 10000 primes and so on: 

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
40.705882352941174
22.045279383429673
17.62109426211598
15.619414543051187
14.47513863274964
13.73425213148954

To iloraz, jeśli użyję 1.01 jako wykładnika. Oto, co licznik znajduje empirycznie:

ns: Array[Int] = Array(1628, 2929, 23583, 321898, 4291625, 54289190, 660847317)

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
1.799140049140049
8.051553431205189
13.649578085909342
13.332251210010625
12.65003116535112
12.172723833234572

Pierwsze dwie wartości są wartościami odstającymi, ponieważ wprowadziłem stałą korektę dla mojego oszacowania formalnego dla małych wartości (do 1000).

Z sugestią Petera Taylorsa o wersji 1.5 wyglądałoby to tak:

245.2396265560166
98.8566987153728
70.8831374743478
59.26104390040363
52.92941829568069
48.956394784317816

Teraz z moją wartością przechodzę do:

O(263)
res85: Long = 1576

Ale nie jestem pewien, jak blisko mojej funkcji O mogę się zbliżyć do obserwowanych wartości.

Ruby 66 znaków, O (n ^ 2) Wynik - 4356

lazyjest dostępny od Rubiego 2.0 i 1.0/0jest fajną sztuczką, aby uzyskać nieskończony zasięg:

(2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j==0}}.take(n).to_a

Ruby, 84 znaki, 84 bajty, wynik?

Ten jest prawdopodobnie trochę za nowicjuszem na te części, ale dobrze się bawiłem. Po prostu zapętla się, aż f(znalezione liczby pierwsze) będzie równa npożądanej liczbie liczb pierwszych do znalezienia.

Zabawne jest to, że dla każdej pętli tworzy tablicę od 2 do jeden mniejszą niż liczba sprawdzana. Następnie mapuje każdy element w tablicy, aby był modułem pierwotnej liczby i elementu, i sprawdza, czy którykolwiek z wyników jest równy zero.

Nie mam też pojęcia, jak to zdobyć.

Aktualizacja

Kod skompresowany i zawierał (całkowicie dowolną) wartość dla n

n,f,i=5**5,0,2
until f==n;f+=1;p i if !(2...i).to_a.map{|j|i%j}.include?(0);i+=1;end

Oryginalny

f, i = 0, 2
until f == n
  (f += 1; p i) if !(2...i).to_a.map{|j| i % j}.include?(0)
  i += 1
end

i += 1Bit i untilpętla są swego rodzaju skoki na mnie jako obszary do poprawy, ale na tym torze Jestem rodzaj zakleszczony. W każdym razie fajnie było o tym myśleć.

Scala, 124 znaki

object Q extends App{Stream.from(2).filter(p=>(2 to p)takeWhile(i=>i*i<=p)forall{p%_!= 0})take(args(0)toInt)foreach println}

Prosty podział próbny do pierwiastka kwadratowego. Złożoność powinna zatem wynosić O (n ^ (1,5 + epsilon))

124 ^ 1,5 <1381, więc to byłby mój wynik?

Perl - 94 znaków, O (n log (n)) - Wynik: 427

perl -wle '$n=1;$t=1;while($n<$ARGV[0]){$t++;if((1x$t)!~/^1?$|^(11+?)\1+$/){print $t;$n++;}}'

Python - 113 znaków

import re
z = int(input())
n=1
t=1
while n<z:
    t+=1
    if not re.match(r'^1?$|^(11+?)\1+$',"1"*t):
        print t
        n+=1

AWK, 96 86 bajtów

Podtytuł: Look Mom! Tylko dodawanie i księgowość!

Plik fsoe3.awk:

{for(n=2;l<$1;){if(n in L)p=L[n]
else{print p=n;l++}
for(N=p+n++;N in L;)N+=p
L[N]=p}}

Biegać:

$ awk -f fsoe3.awk <<< 5
2
3
5
7
11
$ awk -f fsoe3.awk <<< 1000 | wc -l
1000

BASH, 133 bajty

Plik x.bash:

a=2
while((l<$1));do if((b[a]))
then((c=b[a]));else((c=a,l++));echo $a;fi;((d=a+c))
while((b[d]));do((d+=c));done
((b[d]=c,a++));done

Biegać:

$ bash x.bash 5
2
3
5
7
11
$ bash x.bash 1000 | wc -l
1000

Liczby pierwsze oblicza się, pozwalając znalezionym liczbom pierwszym przeskakiwać na „taśmie liczb całkowitych dodatnich”. Zasadniczo jest to serializowane sito Eratostenesa.

from time import time as t

L = {}
n = 2
l = 0

t0=t()

while l<1000000:

        if n in L:
                P = L[n]
        else:
                P = n
                l += 1
                print t()-t0

        m = n+P
        while m in L:
                m += P
        L[m] = P

        n += 1

... jest tym samym algorytmem w Pythonie i wypisuje czas, w którym lznaleziono -tą liczbę pierwszą zamiast samej liczby pierwszej.

Dane wyjściowe wykreślone za pomocą gnuplotdają następujące wyniki:

Skoki prawdopodobnie mają coś wspólnego z opóźnieniami we / wy plików z powodu zapisywania buforowanych danych na dysku ...

Wykorzystanie znacznie większej liczby liczb pierwszych do wprowadzenia spowoduje dodatkowe opóźnienia zależne od systemu, np. Tablica reprezentująca „taśmę dodatnich liczb całkowitych” rośnie stale i prędzej czy później sprawi, że każdy komputer będzie żądał więcej pamięci RAM (lub późniejszej wymiany).

... więc zrozumienie złożoności poprzez spojrzenie na dane eksperymentalne nie bardzo pomaga ... :-(

Teraz licząc dodatki potrzebne do znalezienia nliczb pierwszych:

cells = {}
current = 2
found = 0

additons = 0

while found < 10000000:

        if current in cells:
                candidate = cells[current]
                del cells[current] # the seen part is irrelevant
        else:
                candidate = current
                found += 1 ; additons += 1
                print additons

        destination = current + candidate ; additons += 1
        while destination in cells:
                destination += candidate ; additons += 1
        cells[destination] = candidate

        current += 1 ; additons += 1

Scala 121 (99 bez płyty głównej klasy Main)

object Q extends App{Stream.from(2).filter{a=>Range(2,a).filter(a%_==0).isEmpty}.take(readLine().toInt).foreach(println)}

Python 3, 117 106 bajtów

To rozwiązanie jest nieco trywialne, ponieważ zwraca 0, gdzie liczba nie jest liczbą pierwszą, ale mimo to opublikuję:

r=range
for i in[2]+[i*(not 0 in[i%j for j in r(3,int(i**0.5)+1,2)])for i in r(3,int(input()),2)]:print(i)

Ponadto nie jestem pewien, jak obliczyć złożoność algorytmu. Proszę nie głosować z tego powodu. Zamiast tego bądź miły i komentuj, jak mógłbym to wypracować. Powiedz mi też, jak mogę to skrócić.

Haskell (52² = 2704)

52`take`Data.List.nubBy(((1<).).gcd)[2..]`forM_`print

Perl 6, 152 bajty, O (n log n log (n log n) log (log (n log n))) (?), 9594.79 punktów

Według tej strony złożoność bitowa znalezienia wszystkich liczb pierwszych do n wynosi O (n log n log log n); powyższa złożoność wykorzystuje fakt, że n-ta liczba pierwsza jest proporcjonalna do n log n.

my \N=+slurp;my \P=N*(N.log+N.log.log);my @a=1 xx P;for 2..P.sqrt ->$i {if @a[$i] {@a[$_*$i]=0 for $i..P/$i}};say $_[1] for (@a Z ^P).grep(*[0])[2..N+1]

Groovy (50 bajtów) - O (n * sqrt (n)) - wynik 353,553390593

{[1,2]+(1..it).findAll{x->(2..x**0.5).every{x%it}}​}​

Pobiera in i wyświetla wszystkie liczby od 1 do n, które są liczbą pierwszą.

Algorytm, który wybrałem, wyprowadza tylko liczby pierwsze n> 2, więc wymagane jest dodanie 1,2 na początku.

Awaria

x%it - Implikowana prawda, jeśli nie jest podzielna, fałsz, jeśli tak jest.

(2..x**0.5).every{...}- Dla wszystkich wartości między 2 a sqrt (x) upewnij się, że nie są podzielne, aby to zwróciło true, musi zwrócić true dla każdego .

(1..it).findAll{x->...} - Dla wszystkich wartości od 1 do n znajdź wszystkie, które spełniają kryteria niepodzielności między 2 a sqrt (n).

{[1,2]+...}​ - Dodaj 1 i 2, ponieważ są zawsze pierwsze i nigdy nie są objęte algorytmem.

Rakieta 155 bajtów

(let p((o'(2))(c 3))(cond[(>=(length o)n)(reverse o)][(ormap(λ(x)(= 0(modulo c x)))
(filter(λ(x)(<= x(sqrt c)))o))(p o(add1 c))][(p(cons c o)(add1 c))]))

Przechowuje listę znalezionych liczb pierwszych i sprawdza podzielność każdej kolejnej liczby przez już znalezione liczby pierwsze. Co więcej, sprawdza tylko pierwiastek kwadratowy z testowanej liczby, ponieważ to wystarczy.

Nie golfowany:

(define(nprimes n)
  (let loop ((outl '(2))                   ; outlist having primes being created
             (current 3))                  ; current number being tested
  (cond
    [(>= (length outl) n) (reverse outl)]  ; if n primes found, print outlist.
    [(ormap (λ(x) (= 0 (modulo current x))) ; test if divisible by any previously found prime
            (filter                         ; filter outlist till sqrt of current number
             (λ(x) (<= x (sqrt current)))
             outl))
     (loop outl (add1 current)) ]           ; goto next number without adding to prime list
    [else (loop (cons current outl) (add1 current))] ; add to prime list and go to next number
    )))

Testowanie:

(nprimes 35)

Wydajność:

'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149)

awk 45 (złożoność N ^ 2)

inny awk, dla liczb pierwszych do 100 takich jak ten

awk '{for(i=2;i<=sqrt(NR);i++) if(!(NR%i)) next} NR>1' <(seq 100)

Kod liczony część golfa jest

{for(i=2;i<=sqrt(NR);i++)if(!(NR%i))next}NR>1

które można umieścić w pliku skryptu i uruchomić jako awk -f prime.awk <(seq 100)

JavaScript, 61 znaków

f=(n,p=2,i=2)=>p%i?f(n,p,++i):i==p&&n--&alert(p)||n&&f(n,++p)

Nieco gorzej niż O (n ^ 2), zabraknie miejsca na stosie dla dużego n.