Les règles sont simples:

• Les premiers n nombres premiers (pas les nombres premiers inférieurs à n ) doivent être imprimés sur la sortie standard séparés par des retours à la ligne (les nombres premiers doivent être générés dans le code)
• les nombres premiers ne peuvent pas être générés par une fonction intégrée ou par le biais d'une bibliothèque , c'est-à-dire que l'utilisation d'une fonction intégrée ou d'une bibliothèque telle que prime = get_nth_prime (n), is_a_prime (nombre) ou factorlist = list_all_factors (nombre) ne sera pas très créative.

• Scoring - Disons que nous définissons Score = f ([nombre de caractères dans le code]), O ( f (n)) étant la complexité de votre algorithme où n est le nombre de nombres premiers qu'il trouve. Ainsi, par exemple, si vous avez un code de 300 caractères avec une complexité O (n ^ 2), le score est de 300 ^ 2 = 90000 , pour 300 caractères avec O (n * ln (n)), le score devient 300 * 5,7 = 1711,13 ( supposons que tous les journaux soient des journaux naturels pour plus de simplicité)

• Utilisez n'importe quel langage de programmation existant, le score le plus bas gagne

Edit: le problème a été changé de trouver 'premiers 1000000 premiers' à 'premiers n premiers' en raison d'une confusion sur ce que 'n' dans O (f (n)) est, n est le nombre de nombres premiers que vous trouvez (trouver des nombres premiers est le problème ici et donc la complexité du problème dépend du nombre de nombres premiers trouvés)

Remarque: pour clarifier certaines confusions sur la complexité, si 'n' est le nombre de nombres premiers que vous trouvez et 'N' est le nième nombre premier trouvé, la complexité en termes de n est et N ne sont pas équivalents, c'est-à-dire O (f (n))! = O (f (N)) as, f (N)! = Constant * f (n) et N! = Constant * n, car nous savons que la nième fonction première n'est pas linéaire, je pensais que puisque nous trouvions 'n' la complexité des nombres premiers devrait être facilement exprimable en termes de «n».

Comme l'a souligné Kibbee, vous pouvez visiter ce site pour vérifier vos solutions ( voici l'ancienne liste de documents Google)

Veuillez les inclure dans votre solution -

• la complexité de votre programme (incluez une analyse de base si elle n'est pas anodine)

• longueur de caractère du code

• le score calculé final

Ceci est ma première question CodeGolf donc, s'il y a une erreur ou une faille dans les règles ci-dessus, veuillez les signaler.

Python (129 caractères, O (n * log log n), score de 203,948)

Je dirais que le tamis d'Ératosthène est la voie à suivre. Très simple et relativement rapide.

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

Code amélioré d'avant.

Python ( 191 156 152 caractères, O (n * log log n) (?), Score de 252.620 (?))

Je ne peux pas du tout calculer la complexité, c'est la meilleure approximation que je puisse donner.

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)))est la limite supérieure du ne nombre premier.

Haskell, taux de croissance empirique n ^ 1,1, 89 caractères, score 139 (?)

Ce qui suit fonctionne à l'invite GHCi lorsque la bibliothèque générale qu'il utilise a été précédemment chargée. Imprimer n -ième prime, basé sur 1:

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

C'est le tamis illimité d'Eratosthène, utilisant une bibliothèque à usage général pour les listes ordonnées. Complexité empirique entre 100 000 et 200 000 nombres premiers O(n^1.1). S'adapte à O(n*log(n)*log(log n)).

À propos de l'estimation de la complexité

J'ai mesuré le temps d'exécution pour des nombres premiers de 100k et 200k, puis calculé logBase 2 (t2/t1), ce qui a produit n^1.09. Définir g n = n*log n*log(log n), calculer logBase 2 (g 200000 / g 100000)donne n^1.12.

Ensuite 89**1.1 = 139, bien que g(89) = 600. --- (?)

Il semble que pour la notation, le taux de croissance estimé devrait être utilisé à la place de la fonction de complexité elle-même. Par exemple, g2 n = n*((log n)**2)*log(log n)est beaucoup mieux que n**1.5, mais pour 100 caractères, les deux produisent respectivement le score de 3239et 1000. Ça ne peut pas être vrai. L'estimation sur 200k / 100k donne logBase 2 (g2 200000 / g2 100000) = 1.2et donc le score de 100**1.2 = 251.

En outre, je ne cherche pas à imprimer tous les nombres premiers, juste le n premier -ème place.

Aucune importation, 240 caractères. n ^ 1,15 taux de croissance empirique, score 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 caractères, O (n ^ 2), score 7921

Le score le plus élevé par nombre de chars gagne, non? Modifié pour le premier N. Aussi, je ne peux apparemment pas utiliser de calculatrice, donc mon score n'est pas aussi mauvais que je le pensais. (en utilisant la complexité de la division d'essai de base telle que trouvée dans la source ci-dessous).

Selon Will Ness, ce qui suit n'est pas un programme Haskell complet (il repose en fait sur le REPL). Ce qui suit est un programme plus complet avec un pseudo-tamis (les importations enregistrent en fait un caractère, mais je n'aime pas les importations dans le code golf).

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

Cette version est sans aucun doute (n ^ 2). L'algorithme n'est qu'une version golfique du `` tamis '' naïf, comme on le voit ici Old ghci 1 liner

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

Laissant l'ancienne réponse tricherie parce que la bibliothèque à laquelle elle est liée est plutôt sympa.

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

Voir ici pour une implémentation et les liens pour la complexité temporelle. Malheureusement, les roues ont un temps de recherche log (n), ce qui nous ralentit d'un facteur.

C #, 447 caractères, octets 452, score?

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

scriptcs Variant, 381 caractères, 385 octets, score?

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

Si vous installez des scriptcs, vous pouvez l'exécuter.

PS J'ai écrit ceci dans Vim :D

GolfScript (45 caractères, score revendiqué ~ 7708)

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

Cela fait une division d'essai simple par nombres premiers. Si près de la pointe de Ruby (c'est-à-dire en utilisant 1.9.3.0), l'arithmétique utilise la multiplication Toom-Cook 3, donc une division d'essai est O (n ^ 1,465) et le coût global des divisions est O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)†. Cependant, dans GolfScript, l'ajout d'un élément à un tableau nécessite de copier le tableau. J'ai optimisé cela pour copier la liste des nombres premiers uniquement lorsqu'il trouve un nouveau nombre premier, donc seulement nau total. Chaque opération de copie est des O(n)éléments de taille O(ln(n ln n)) = O(ln n)†, ce qui donne O(n^2 ln n).

Et cela, garçons et filles, est la raison pour laquelle GolfScript est utilisé pour le golf plutôt que pour une programmation sérieuse.

† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). J'aurais dû repérer cela avant de commenter divers articles ...

C'est tellement facile, même mon éditeur de texte peut le faire!

Vim: 143 frappes (115 actions): O (n ^ 2 * log (n)): Score: 101485.21

Soumission:

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

Entrée: N doit être sur la première ligne d'un document vierge. Après cela, chaque nombre premier de 2 à N sera une ligne distincte.

Exécution des commandes:

Tout d'abord, notez que toutes les commandes avec un curseur devant elles signifient que vous devez maintenir Ctrl et taper la lettre suivante (par exemple ^ V est Ctrl-vet ^ R est Ctrl-r).

Cela écrasera tout ce qui se trouve dans vos registres @a, @b, @d et @p.

Parce que cela utilise des qcommandes, il ne peut pas simplement être placé dans une macro. Cependant, voici quelques conseils pour l'exécuter.

• qpqqdq efface simplement les registres
• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddva créer une liste de numéros 2 à N + 1. Ceci est une pause entre les deux parties principales, donc une fois cela fait, vous ne devriez plus avoir à le refaire
• 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@pne doit être tapé en une seule fois. Essayez d'éviter le retour arrière car cela pourrait gâcher quelque chose.
  • Si vous faites une erreur, tapez qdqqpqpuis réessayez cette ligne.

Pour le grand N, c'est très lent. Il a fallu environ 27 minutes pour exécuter N = 5000; considérez-vous comme prévenu.

Algorithme:

Cela utilise un algorithme récursif de base pour trouver des nombres premiers. Étant donné une liste de tous les nombres premiers compris entre 1 et A, A + 1 est premier s'il n'est divisible par aucun des nombres de la liste des nombres premiers. Commencez par A = 2 et ajoutez des nombres premiers à la liste lorsqu'ils sont trouvés. Après N récursions, la liste contiendra tous les nombres premiers jusqu'à N.

Complexité

Cet algorithme a une complexité de O (nN), où N est le nombre d'entrée et n est le nombre de nombres premiers jusqu'à N. Chaque récursivité teste n nombres, et N récursions sont effectuées, donnant O (nN).

Cependant, N ~ n * log (n), donnant la complexité finale en O (n ² * log (n)) ( https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number )

Explication

Il n'est pas facile de discerner le flux du programme à partir des commandes vim, donc je l'ai réécrit en Python en suivant le même flux. Comme le code Vim, le code python sortira en erreur lorsqu'il atteindra la fin. Python n'aime pas trop la récursivité; si vous essayez ce code avec N> 150 ou plus, il atteindra la profondeur de récursivité maximale

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

Maintenant, pour décomposer les frappes réelles!

• qpqqdqEfface les registres @d et @p. Cela garantira que rien ne s'exécute lors de la configuration de ces macros récursives.

• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddTransforme l'entrée en une liste de nombres de 2 à N + 1. L'entrée N + 1 est supprimée comme effet secondaire de la configuration de la macro @d.

  • Plus précisément, écrit une macro qui incrémente un nombre, puis la copie sur la ligne suivante, puis elle écrit un 1 et exécute cette macro N fois.

• mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qécrit la macro @d, qui implémente la fonction d () ci-dessus. Les instructions "If" sont intéressantes à implémenter dans Vim. En utilisant l'opérateur de recherche *, il est possible de choisir un certain chemin à suivre. Briser la commande plus loin, nous obtenons

  • mpqdDéfinissez la marque p ici et commencez à enregistrer la macro @d. La marque p doit être définie, il y a donc un point connu vers lequel sauter lorsque cela s'exécute
  • o^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc> Écrit le texte de l'instruction if / else
  • 0*w*wyiWdd@0 exécute réellement l'instruction if.
  • Avant d'exécuter cette commande, la ligne contiendra @a @b 0 0 `pj@p @a 0 (@a%@b) `pdd@p 0 `dj@d
  • 0 déplace le curseur au début de la ligne

  • *w*w Déplace le curseur sur le code à exécuter ensuite

    1. si @a == @b, c'est-à- `pj@pdire qui passe au numéro suivant pour @a et exécute @p dessus.
    2. si @a! = @b et @ a% @ b == 0, c'est-à- `pdd@pdire qui supprime le nombre actuel @a, puis exécute @p sur le suivant.
    3. si @a! = @b et @ a %% b! = 0, c'est-à- `dj@ddire qui vérifie le nombre suivant pour @b pour voir si c'est un facteur de @a

  • yiWdd@0 met la commande dans le registre 0, supprime la ligne et exécute la commande

  • q termine l'enregistrement de la macro @d

• Lors de sa première exécution, la `pdd@pcommande est exécutée, supprimant la ligne N + 1.

• qpmp"aywgg@dq écrit la macro @p, qui enregistre le nombre sous le curseur, puis passe à la première entrée et exécute @d dessus.

• gg@p exécute en fait @p pour qu'il itère sur tout le fichier.

QBASIC, 98 caractères, Complexité N Sqrt (N), Score 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 caractères

Mis à jour pour s'adapter aux nouvelles exigences. 25% du code traitent de la recherche d'une limite supérieure raisonnable pour calculer les nombres premiers ci-dessous.

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

J'ai aussi un tamis.

Voici un test empirique des coûts de calcul, non testé pour l'analyse:

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 

conduit aux décomptes suivants:

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

Je ne sais pas comment calculer le score. Vaut-il la peine d'écrire 5 caractères supplémentaires?

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)

Pour un n plus grand, cela réduit les calculs d'environ 16% dans cette plage, mais afaik pour la formule de score, nous ne considérons pas les facteurs constants?

nouvelles considérations Big-O:

Pour trouver 1 000, 10 000, 100 000 nombres premiers et ainsi de suite, j'utilise une formule sur la densité des nombres premiers x => (math.log (x) * x * 1,3 qui détermine la boucle externe que j'exécute.

Donc pour les valeurs i dans 1 à 6 => NPrimes (10 ^ i) court 9399, 133768 ... fois la boucle externe.

J'ai trouvé cette fonction O de manière itérative avec l'aide du commentaire de Peter Taylor, qui a suggéré une valeur beaucoup plus élevée pour l'exponentiation, au lieu de 1,01, il a suggéré 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

Ce sont les quotients, si j'utilise 1.01 comme exposant. Voici ce que le compteur trouve empiriquement:

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

Les deux premières valeurs sont aberrantes, car j'ai fait une correction constante pour mon formulaire d'estimation pour les petites valeurs (jusqu'à 1000).

Avec la suggestion de Peter Taylors de 1,5, cela ressemblerait à:

245.2396265560166
98.8566987153728
70.8831374743478
59.26104390040363
52.92941829568069
48.956394784317816

Maintenant, avec ma valeur, j'arrive à:

O(263)
res85: Long = 1576

Mais je ne sais pas, à quel point je peux me rapprocher de ma fonction O des valeurs observées.

Ruby 66 caractères, O (n ^ 2) Score - 4356

lazyest disponible depuis Ruby 2.0, et 1.0/0est une astuce intéressante pour obtenir une plage infinie:

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

Ruby, 84 caractères, 84 octets, score?

Celui-ci est probablement un peu trop novice pour ces parties, mais j'ai eu du plaisir à le faire. Il boucle simplement jusqu'à ce que f(nombres premiers trouvés) soit égal au nnombre souhaité de nombres premiers à trouver.

La partie amusante est que pour chaque boucle, il crée un tableau de 2 à un de moins que le nombre inspecté. Ensuite, il mappe chaque élément du tableau pour être le module du nombre d'origine et de l'élément, et vérifie si l'un des résultats est nul.

De plus, je n'ai aucune idée de comment le marquer.

Mise à jour

Code compacté et inclus une valeur (totalement arbitraire) pour 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

Original

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

Le i += 1bit et la untilboucle me sautent aux yeux comme des domaines à améliorer, mais sur cette piste, je suis en quelque sorte coincé. Quoi qu'il en soit, c'était amusant d'y penser.

Scala, 124 caractères

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}

Division d'essai simple jusqu'à la racine carrée. La complexité devrait donc être O (n ^ (1,5 + epsilon))

124 ^ 1,5 <1381, ce serait donc mon score je suppose?

Perl - 94 caractères, O (n log (n)) - Score: 427

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

Python - 113 caractères

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 octets

Sous-titre: Regardez maman! Ajout seulement et un peu de comptabilité!

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

Courir:

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

BASH, 133 octets

Fichier 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

Courir:

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

Les nombres premiers sont calculés en laissant les nombres premiers déjà trouvés sauter sur la "bande d'entiers positifs". Fondamentalement, c'est un tamis sérialisé d'Eratosthène.

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

... est le même algorithme en Python et affiche le moment où le l-ième nombre premier a été trouvé au lieu du nombre premier lui-même.

La sortie tracée avec gnuplotdonne les résultats suivants:

Les sauts ont probablement quelque chose à voir avec les retards d'E / S de fichiers dus à l'écriture de données tamponnées sur le disque ...

L'utilisation d'un plus grand nombre de nombres premiers pour trouver, entraînera des retards supplémentaires dépendants du système dans le jeu, par exemple, le tableau représentant la "bande d'entiers positifs" croît continuellement et tôt ou tard, chaque ordinateur pleurera pour plus de RAM (ou échange ultérieur).

... donc avoir une idée de la complexité en regardant les données expérimentales n'aide pas vraiment beaucoup ... :-(

Maintenant, comptons les ajouts nécessaires pour trouver des nnombres premiers:

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 sans passe-partout de classe principale)

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 octets

Cette solution est légèrement triviale, car elle génère 0 où un nombre n'est pas premier, mais je le publierai quand même:

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)

De plus, je ne sais pas comment calculer la complexité d'un algorithme. S'il vous plaît, ne votez pas à cause de cela. Au lieu de cela, soyez gentil et commentez comment je pourrais le résoudre. Aussi, dites-moi comment je pourrais raccourcir cela.

Haskell (52² = 2704)

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

Perl 6, 152 octets, O (n log n log (n log n) log (log (n log n))) (?), 9594,79 points

Selon cette page , la complexité en bits de trouver tous les nombres premiers jusqu'à n est O (n log n log log n); la complexité ci-dessus utilise le fait que le nième nombre est proportionnel à 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 octets) - O (n * sqrt (n)) - Score 353,553390593

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

Prend n et sort tous les nombres de 1 à n qui sont premiers.

L'algorithme que j'ai choisi ne produit que des nombres premiers n> 2, il est donc nécessaire d'ajouter 1,2 au début.

Panne

x%it - Vérité implicite si elle n'est pas divisible, fausse si elle l'est.

(2..x**0.5).every{...}- Pour toutes les valeurs comprises entre 2 et sqrt (x), assurez-vous qu'elles ne sont pas divisibles, pour que cela renvoie true, vous devez renvoyer true pour chaque .

(1..it).findAll{x->...} - Pour toutes les valeurs comprises entre 1 et n, trouvez toutes celles qui correspondent au critère d'être non divisible entre 2 et sqrt (n).

{[1,2]+...}​ - Ajoutez 1 et 2, car ils sont toujours premiers et ne sont jamais couverts par l'algorithme.

Raquette 155 octets

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

Il conserve une liste des nombres premiers trouvés et vérifie la divisibilité de chaque nombre suivant par les nombres premiers déjà trouvés. De plus, il ne vérifie que jusqu'à la racine carrée du nombre testé car cela suffit.

Non golfé:

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

Essai:

(nprimes 35)

Sortie:

'(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 (complexité N ^ 2)

un autre awk, pour des nombres premiers jusqu'à 100, utilisez comme ceci

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

partie de code de golf compté est

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

qui peut être placé dans un fichier script et exécuté en tant que awk -f prime.awk <(seq 100)

Javascript, 61 caractères

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

Un peu pire que O (n ^ 2), il manquera d'espace de pile pour les grands n.