Calcul et impression du nième nombre premier

Pour calculer le n-ième premier, je connais deux variantes principales.

La manière simple

C'est-à-dire compter tous les nombres premiers à partir de 2 tels que vous les trouvez jusqu'à ce que vous ayez atteint le N^TH désiré.

Cela peut être fait avec différents niveaux de sophistication et d'efficacité, et il y a deux façons conceptuellement différentes de le faire. Le premier est

Tester la primalité de tous les nombres en séquence

Ce serait accompli par une fonction de pilote comme

public static int nthPrime(int n) {
    int candidate, count;
    for(candidate = 2, count = 0; count < n; ++candidate) {
        if (isPrime(candidate)) {
            ++count;
        }
    }
    // The candidate has been incremented once after the count reached n
    return candidate-1;
}

Et la partie intéressante qui détermine l'efficacité est la fonction isPrime.

La voie évidente pour un contrôle de primalité, étant donné la définition d'un premier comme un nombre supérieur à 1 qui n'est divisible que par 1 et par lui - même que nous avons appris à l'école1, est

Section de première instance

La traduction directe de la définition en code est

private static boolean isPrime(int n) {
    for(int i = 2; i < n; ++i) {
        if (n % i == 0) {
            // We are naive, but not stupid, if
            // the number has a divisor other
            // than 1 or itself, we return immediately.
            return false;
        }
    }
    return true;
}

Mais, comme vous le découvrirez bientôt si vous l'Essayez, son la simplicité est accompagné par la lenteur. Avec ce test de primalité, vous pouvez trouver le 1000^th premier, 7919, en quelques millisecondes (environ 20 sur mon ordinateur), mais trouver le 10000^TH premier, 104729, prend des secondes (~2.4 s), le 100000^th premier,1299709, plusieurs minutes (environ 5), le millionième premier, 15485863, prendrait environ huit heures et 179424673, semaines, et ainsi de suite. La complexité d'exécution est pire que quadratique-Θ (n2 * log et).

Donc nous aimerions accélérer un peu le test de primalité. Une étape que beaucoup de gens prennent est la réalisation qu'un diviseur de n (autre que n lui-même) peut être au plus n/2. Si nous utilisons ce fait et que la boucle de division d'essai ne s'exécute que sur n/2 au lieu de n-1, comment le temps d'exécution de l'algorithme change-t-il? Pour les nombres composites, la limite de boucle inférieure ne change rien. Pour les nombres premiers, le nombre de divisions d'essai est réduit de moitié, donc globalement, le temps d'exécution devrait être réduit d'un facteur légèrement inférieur à 2. Si vous l'essayez, vous constaterez que le temps d'exécution est presque exactement divisé par deux, donc presque tout le temps est consacré à vérifier la primalité des nombres premiers malgré qu'il y ait beaucoup plus de composites que de nombres premiers.

Maintenant, cela n'a pas beaucoup aidé si nous voulons trouver le cent millionième premier, donc nous devons faire mieux. En essayant de réduire davantage la limite de boucle, voyons pour quels nombres la limite supérieure de n/2 est réellement nécessaire. Si n/2 est un diviseur de n, puis n/2 est un nombre entier, en d'autres termes, n est divisible par 2. Mais alors la boucle ne passe pas au-delà de 2, donc elle n'atteint jamais (sauf n = 4) n/2. Jolly good, alors quel est le prochain plus grand diviseur possible de n? Pourquoi, n/3, bien sûr. Mais n/3 ne peut être un diviseur de n si c'est un entier, en d'autres termes, si n est divisible par 3. Ensuite, la boucle sortira à 3 (ou avant, à 2) et n'atteindra jamais n/3 (sauf pour n = 9). Le prochain plus grand diviseur possible ...

Accrocher sur une minute! Nous avons 2 <-> n/2 et 3 <-> n/3. les diviseurs de n viennent par paires.

Si nous considérons la paire (d, n/d) correspondant à la diviseurs de n, soit d = n/d, soit d = √n, ou l'un d'eux, dire d, est plus petit que l'autre. Mais alors d*d < d*(n/d) = n et d < √n. Chaque paire de diviseurs de n contient (au moins) qui ne dépasse pas √n.

Si n est composite, son plus petit diviseur non trivial ne dépasse pas √n.

Nous pouvons donc réduire la limite de boucle à √n, ce qui réduit la complexité d'exécution de l'algorithme. Il devrait maintenant être Θ (n^1.5 * √(log n)), mais empiriquement, il semble évoluer un peu mieux-cependant, il n'y a pas assez de données pour tirer des conclusions fiables des résultats empiriques.

Qui trouve le millionième premier en environ 16 secondes, le dix-millionième en un peu moins de neuf minutes, et il trouverait le cent millionième en quatre heures et demie. C'est encore lent, mais loin des dix ans qu'il faudrait à la division de première instance naïve.

Comme il y a des carrés de nombres premiers et des produits de deux nombres premiers proches, comme 323 = 17 * 19, nous ne pouvons pas réduire la limite pour la boucle de division d'essai ci-dessous √n. Par conséquent, tout en restant à la division de première instance, nous devons chercher d'autres moyens d'améliorer l'algorithme maintenant.

Une chose facile à voir est qu'aucun Premier autre que 2 n'est même, nous n'avons donc besoin que de vérifier les nombres impairs après avoir pris soin de 2. Cela ne fait pas beaucoup de différence, cependant, puisque les nombres pairs sont les moins chers à trouver composite - et la majeure partie du temps est encore consacré à vérifier la primalité des nombres premiers. Cependant, si nous regardons les nombres pairs comme des diviseurs candidats, nous voyons que si n est divisible par un nombre pair, n lui-même doit être pair, donc (à l'exception de 2) il aura été reconnu comme composite avant la division par un nombre pair plus grand que 2 est tenté. Ainsi, toutes les divisions par des nombres pairs supérieurs à 2 qui se produisent dans l'algorithme doivent nécessairement laisser un reste non nul. Nous pouvons ainsi omettre ces divisions et vérifier la divisibilité seulement par 2 et les nombres impairs de 3 à √n. Cela réduit de moitié (pas tout à fait exactement) le nombre de divisions nécessaires pour déterminer un nombre comme Premier ou composite et donc le temps de fonctionnement. C'est un bon début, mais pouvons-nous faire mieux?

Une autre grande famille de nombres est les multiples sur 3. Chaque troisième division, nous l'exécuter par un multiple de 3, mais si n est divisible par l'un d'eux, il est aussi divisible par 3, et donc pas de division par 9, 15, 21, ... que nous effectuons dans notre algorithme laissera jamais un reste de 0. Alors, comment pouvons-nous sauter ces divisions? Eh bien, les nombres divisibles par Ni 2 Ni 3 sont précisément les nombres de la forme 6*k ± 1. À partir de 5 (puisque nous ne sommes intéressés que par des nombres supérieurs à 1), Ils sont 5, 7, 11, 13, 17, 19, ...- l'étape de l'un à l' le suivant alterne entre 2 et 4, ce qui est assez facile, donc nous pouvons utiliser

private static boolean isPrime(int n) {
    if (n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    int step = 4, m = (int)Math.sqrt(n) + 1;
    for(int i = 5; i < m; step = 6-step, i += step) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Cela nous donne une autre accélération d'un facteur de (près de) 1,5, donc nous aurions besoin d'environ une heure et demie pour le cent-millionième premier.

Si nous continuons cette route, l'étape suivante est l'élimination des multiples de 5. Les numéros coprime à 2, 3 et 5 sont les numéros de la forme

30*k + 1, 30*k + 7, 30*k + 11, 30*k + 13, 30*k + 17, 30*k + 19, 30*k + 23, 30*k + 29

Donc, nous n'aurions besoin que de diviser par huit numéros sur trente (plus les trois plus petits premier). Les étapes à partir de l'une à l'autre, à partir de 7, cycle par le biais de 4, 2, 4, 2, 4, 6, 2, 6. C'est encore assez facile à implémenter et donne une autre accélération d'un facteur de 1,25 (moins un peu pour un code plus compliqué). Aller plus loin, les multiples de 7 seraient éliminés, laissant 48 sur 210 nombres à diviser par, puis 11 (480/2310), 13 (5760/30030) et ainsi de suite. Chaque premier p dont les multiples sont éliminés donne une accélération de (presque) p/(p-1), de sorte que le rendement diminue alors que le coût (complexité du code, espace pour la table de recherche pour les étapes) augmente avec chaque prime.

En général, on s'arrêterait bientôt, après avoir éliminé les multiples de peut-être six ou sept nombres premiers (ou même moins). Ici, cependant, nous pouvons suivre jusqu'à la fin, lorsque les multiples de tous les nombres premiers ont été éliminés et que seuls les nombres premiers sont laissés comme candidats diviseurs. Puisque nous trouvons tous les nombres premiers dans l'ordre, chaque premier est trouvé avant qu'il ne soit nécessaire en tant que candidat diviseur et peut alors être stocké pour une utilisation future. Cela réduit la complexité algorithmique à - si je n'ai pas mal calculé-O (n^1.5 / √(log n)). Au prix de l'utilisation de l'espace pour stocker les nombres premiers.

Avec la division de première instance, c'est aussi bon que possible, vous devez essayer de diviser par tous les nombres premiers à √n ou la première division n pour déterminer la primalité de n. Qui trouve le cent millionième prime dans environ une demi-heure ici.

Alors, que diriez-vous de

Primalité rapide essais

Les nombres premiers ont d'autres propriétés que l'absence de diviseurs non triviaux que les nombres composites n'ont généralement pas. De telles propriétés, si elles sont rapides à vérifier, peuvent constituer la base de tests de primalité probabilistes ou déterministes. L'archétype de cette propriété est associé au nom de Pierre de Fermat, qui, au début du 17^ème siècle, a constaté que

Si p est un nombre premier, alors p est un diviseur de a^p-un) pour tous a.

Ceci-le soi-disant "petit théorème" de Fermat-est, dans la formulation équivalente

Soit {[51] } un premier et a non divisible par p. Alors p divise^p-1 - 1.

La base de la plupart des tests de primalité rapide répandus (par exemple Miller-Rabin) et des variantes ou analogues de qui apparaissent encore plus (par exemple Lucas-Selfridge).

Donc, si nous voulons savoir si un pas trop petit nombre impair n est premier (même et de petits nombres sont traités efficacement par la division de première instance), nous pouvons choisir n'importe quel nombre a (> 1) qui n'est pas un multiple de n, pour l'exemple 2, et de vérifier si n divise^n-1 - 1. Comme un ^N-1 devient énorme, cela se fait le plus efficacement en vérifiant si a^(n-1) ≡ 1 (mod n), c'est-à-dire par exponentiation modulaire. Si cette congruence ne tient pas, nous savons que n est composite. Si elle tient, cependant, nous ne pouvons pas conclure que n est premier, pour exemple 2^340 ≡ 1 (mod 341), mais 341 = 11 * 31 est composite. Les nombres composites n tels que a^(n-1) ≡ 1 (mod n) sont appelés Pseudoprimes de Fermat pour la base a.

Mais de telles occurrences sont rares. Étant donné toute base a > 1, bien qu'il existe un nombre infini de pseudoprime de Fermat à la base a, ils sont beaucoup plus rares que les nombres premiers réels. Par exemple, il n'y a que 78 pseudoprime de Fermat de base-2 et 76 pseudoprime de Fermat de base-3 en dessous de 100000, mais 9592 nombres premiers. Donc, si l'on choisit un Impair arbitraire n > 1 et un la base arbitraire a > 1 et trouve a^(n-1) ≡ 1 (mod n), Il y a de bonnes chances que n soit réellement premier.

Cependant, nous sommes dans une situation légèrement différente, on nous donne n et ne peut choisir a. Donc, pour un composite Impair n, pour combien a, 1 < a < n-1 peut a^(n-1) ≡ 1 (mod n) tenir? Malheureusement, il existe des nombres composites-les nombres de Carmichael-tels que la congruence est valable pour chaque a coprime à n. Cela signifie que pour identifier un nombre Carmichael comme composite avec le test de Fermat, nous devons choisir une base qui est un multiple de l'un des diviseurs premiers de n - Il n'y a peut-être pas beaucoup de tels multiples.

Mais nous pouvons renforcer le test de Fermat afin que les composites soient détectés de manière plus fiable. Si p est un premier Impair, écrivez p-1 = 2*m. Alors, si 0 < a < p,

a^(p-1) - 1 = (a^m + 1) * (a^m - 1)

Et p divise exactement l'un des deux facteurs (les deux facteurs diffèrent par 2, de sorte que leur plus grand diviseur commun est 1 ou 2). Si m est pair, nous pouvons diviser a^m - 1 dans le même façon. Continuer, si p-1 = 2^s * k avec k Impair, écrire

a^(p-1) - 1 = (a^(2^(s-1)*k) + 1) * (a^(2^(s-2)*k) + 1) * ... * (a^k + 1) * (a^k - 1)

Alors p divise exactement l'un des facteurs. Cela donne lieu au test de Fermat fort,

Soit {[99] } un nombre impair. Écrivez n-1 = 2^s * k avec k Impair. Étant donné tout a avec 1 < a < n-1, si

1. a^k ≡ 1 (mod n) ou
2. a^((2^j)*k) ≡ -1 (mod n) pour tout j avec 0 <= j < s

Alors n est un fort (Fermat) probable premier pour la base a. Une base solide composite a (Fermat) probable premier est appelé un fort (Fermat) pseudoprime pour la base a. Les pseudoprime forts de Fermat sont encore plus rares que les pseudoprime ordinaires de Fermat, en dessous de 1000000, il y a 78498 nombres premiers, 245 pseudoprime de Fermat de base-2 et seulement 46 pseudoprime forts de Fermat de base-2. Plus important encore, pour tout composite Impair n, Il y a au plus (n-9)/4 bases 1 < a < n-1 pour lesquelles n est un pseudoprime Fermat fort.

Si n est un étrange composite, la probabilité que n passe k les tests Fermat forts avec des bases choisies au hasard entre 1 et n-1 (limites exclusives) sont inférieurs à 1/4^k.

Un test de Fermat Fort prend des étapes O(log n), Chaque étape implique une ou deux multiplications de nombres avec des bits O(log N), donc la complexité est O((log n)^3) avec une multiplication naïve [pour les énormes n, des algorithmes de multiplication plus sophistiqués peuvent en valoir la peine].

Le test de Miller-Rabin est le test de Fermat k-fold fort avec des bases choisies au hasard. Il est un test probabiliste, mais pour des limites assez petites, de courtes combinaisons de bases sont connues qui donnent un résultat déterministe.

Les tests de Fermat forts font partie du test déterministe APRCL.

Il est conseillé de précéder ces tests par division d'essai par les premiers petits nombres premiers, car les divisions sont relativement bon marché et que les mauvaises herbes sur la plupart des composites.

Pour le problème de trouver le n^TH prime, dans la plage où tester tous les nombres pour que la primalité soit réalisable, il existe des combinaisons connues de bases qui rendent le test de Fermat fort multiple correct, de sorte que cela donnerait un - O(N*(log n plus rapide)⁴) - algorithme.

Pour n < 2^32, les bases 2, 7 et 61 sont suffisantes pour vérifier la primalité. En utilisant cela, le cent millionième premier se trouve dans environ six minutes.

Éliminer les composites par les diviseurs premiers, Le tamis D'Eratosthène

Au lieu d'étudier les nombres dans l'ordre et vérifier si chacun est PREMIER à partir de zéro, on peut également considérer l'ensemble des nombres pertinents comme une seule pièce et éliminer les multiples d'un nombre premier donné en une seule fois. Ceci est connu comme le tamis D'Eratosthène:

Pour trouver les nombres premiers ne dépassant pas N

1. faire une liste de tous les nombres de 2 à N
2. pour chaque k de 2 à N: si k n'est pas encore passé, c'est le premier; rayez tous les multiples de k comme les composites

Les nombres premiers sont les nombres de la liste qui ne sont pas rayés.

Cet algorithme est fondamentalement différent de la division d'essai, bien que les deux utilisent directement la caractérisation de divisibilité des nombres premiers, contrairement au test de Fermat et aux tests similaires qui utilisent d'autres propriétés des nombres premiers.

Dans la division de première instance, chaque nombre n est jumelé avec tous les nombres premiers ne dépassant pas le plus petit des nombres premiers √n et le plus petit diviseur premier de n. Depuis la plupart des composites ont un très petit diviseur premier, la détection des composites est bon marché ici en moyenne. Mais tester les nombres premiers est coûteux, car il y a relativement beaucoup de nombres premiers en dessous de √n. Bien qu'il y ait beaucoup plus de composites que de nombres premiers, Le coût de test des nombres premiers est si élevé qu'il domine complètement le temps d'exécution global et rend la division d'essai un algorithme relativement lent. Section de première instance pour tous les numéros inférieurs à N prend O (N^1.5 / (log N ² 2) étapes.

Dans le tamis, chaque composite n est jumelé avec l'ensemble de ses diviseurs premiers, mais seulement avec ceux-ci. Ainsi, les nombres premiers sont les nombres bon marché, ils ne sont jamais regardés qu'une seule fois, tandis que les composites sont plus chers, ils sont barrés plusieurs fois. On pourrait croire que puisqu'un tamis contient beaucoup plus de nombres "chers" que de nombres "bon marché", ce serait globalement un mauvais algorithme. Cependant, un nombre composé n'a pas beaucoup de diviseurs premiers distincts - le nombre d'agents de les diviseurs premiers de n sont délimités par log n, mais généralement il est beaucoup plus petit, la moyenne du nombre de diviseurs premiers distincts des nombres <= n est log log n - ainsi même les nombres "chers" dans le tamis ne sont en moyenne pas plus (ou à peine plus) chers que les nombres "bon marché" pour la division de première instance.

Tamisant jusqu'à N, pour chaque premier p, Il y a Θ(N/p) multiples à rayer, de sorte que le nombre total de croisements-off est Θ(∑ (N/p)) = Θ(N * log (log N)). Cela donne beaucoup algorithmes plus rapides pour trouver les nombres premiers jusqu'à N que la division d'essai ou les tests séquentiels avec les tests de primalité plus rapides.

Il y a cependant un inconvénient au tamis, il utilise de la mémoire O(N). (Mais avec un tamis segmenté, cela peut être réduit à O(√N) sans augmenter la complexité temporelle.)

Pour trouver le n^th prime, au lieu des nombres premiers jusqu'à N, Il y a aussi le problème qu'on ne sait pas à l'avance comment loin le tamis devrait atteindre.

Ce dernier peut être résolu en utilisant le théorème des nombres premiers. Le PNT dit

π(x) ~ x/log x (equivalently: lim π(x)*log x/x = 1),

Où π(x) est le nombre de nombres premiers ne dépassant pas x (ici et ci-dessous, log doit être le logarithme naturel, pour les complexités algorithmiques, il n'est pas important quelle base est choisie pour les logarithmes). De cela, il s'ensuit que p(n) ~ n*log n, où p(n) est le n^TH prime, et il y a de bonnes limites supérieures pour p(n) connues de plus profond analyse, en particulier

n*(log n + log (log n) - 1) < p(n) < n*(log n + log (log n)), for n >= 6.

On peut donc l'utiliser comme limite de tamisage, elle ne dépasse pas la cible loin.

L'exigence d'espace O(N) peut être surmontée en utilisant un tamis segmenté. On peut alors enregistrer les nombres premiers ci-dessous √N pour la consommation de mémoire O(√N / log N) et utiliser des segments de longueur croissante (O (√N) lorsque le tamis est proche de N).

Il y a quelques améliorations faciles sur l'algorithme comme indiqué ci-dessus:

1. commencez à croiser les multiples de p seulement à p², pas 2*p
2. éliminer les nombres pairs du tamis
3. éliminer les multiples d'autres petits nombres premiers du tamis

Aucun de ceux-ci ne réduit la complexité algorithmique, mais ils réduisent tous les facteurs constants d'une quantité significative (comme avec la division d'essai, l'élimination des multiples de p donne une accélération moindre pour les plus grands {[51] } tout en augmentant la complexité du code plus que pour les plus petits p).

En utilisant les deux premières améliorations donne

// Entry k in the array represents the number 2*k+3, so we have to do
// a bit of arithmetic to get the indices right.
public static int nthPrime(int n) {
    if (n < 2) return 2;
    if (n == 2) return 3;
    int limit, root, count = 1;
    limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
    root = (int)Math.sqrt(limit) + 1;
    limit = (limit-1)/2;
    root = root/2 - 1;
    boolean[] sieve = new boolean[limit];
    for(int i = 0; i < root; ++i) {
        if (!sieve[i]) {
            ++count;
            for(int j = 2*i*(i+3)+3, p = 2*i+3; j < limit; j += p) {
                sieve[j] = true;
            }
        }
    }
    int p;
    for(p = root; count < n; ++p) {
        if (!sieve[p]) {
            ++count;
        }
    }
    return 2*p+1;
}

Qui trouve le cent millionième premier, 2038074743, en environ 18 secondes. Ce temps peut être réduit à environ 15 secondes (ici, YMMV) en stockant les drapeaux emballés, un bit par drapeau, au lieu de boolean s, car l'utilisation réduite de la mémoire donne une meilleure localisation du cache.

Emballer les drapeaux, en éliminant également les multiples de 3 et en utilisant le bit-twiddling pour un comptage plus rapide,

// Count number of set bits in an int
public static int popCount(int n) {
    n -= (n >>> 1) & 0x55555555;
    n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
    n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
    return (n * 0x01010101) >> 24;
}

// Speed up counting by counting the primes per
// array slot and not individually. This yields
// another factor of about 1.24 or so.
public static int nthPrime(int n) {
    if (n < 2) return 2;
    if (n == 2) return 3;
    if (n == 3) return 5;
    int limit, root, count = 2;
    limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
    root = (int)Math.sqrt(limit);
    switch(limit%6) {
        case 0:
            limit = 2*(limit/6) - 1;
            break;
        case 5:
            limit = 2*(limit/6) + 1;
            break;
        default:
            limit = 2*(limit/6);
    }
    switch(root%6) {
        case 0:
            root = 2*(root/6) - 1;
            break;
        case 5:
            root = 2*(root/6) + 1;
            break;
        default:
            root = 2*(root/6);
    }
    int dim = (limit+31) >> 5;
    int[] sieve = new int[dim];
    for(int i = 0; i < root; ++i) {
        if ((sieve[i >> 5] & (1 << (i&31))) == 0) {
            int start, s1, s2;
            if ((i & 1) == 1) {
                start = i*(3*i+8)+4;
                s1 = 4*i+5;
                s2 = 2*i+3;
            } else {
                start = i*(3*i+10)+7;
                s1 = 2*i+3;
                s2 = 4*i+7;
            }
            for(int j = start; j < limit; j += s2) {
                sieve[j >> 5] |= 1 << (j&31);
                j += s1;
                if (j >= limit) break;
                sieve[j >> 5] |= 1 << (j&31);
            }
        }
    }
    int i;
    for(i = 0; count < n; ++i) {
        count += popCount(~sieve[i]);
    }
    --i;
    int mask = ~sieve[i];
    int p;
    for(p = 31; count >= n; --p) {
        count -= (mask >> p) & 1;
    }
    return 3*(p+(i<<5))+7+(p&1);
}

Trouve le cent millionième prime en environ 9 secondes, ce qui n'est pas insupportablement long.

Il existe d'autres types de tamis premiers, d'un intérêt particulier est le tamis D'Atkin, qui exploite le fait que certaines classes de congruence de nombres premiers (rationnels) sont des composites dans l'anneau des entiers algébriques de certaines extensions quadratiques de ℚ. Ici n'est pas l'endroit pour développer la théorie mathématique, il suffit de dire que le tamis D'Atkin a une complexité algorithmique inférieure à celle du tamis de Eratosthenes et est donc préférable pour les grandes limites (pour les petites limites, un tamis Atkin pas trop optimisé a une surcharge plus élevée et peut donc être plus lent qu'un tamis Eratosthenes optimisé de manière comparable). La bibliothèque primegen de D. J. Bernstein (écrite en C) est bien optimisée pour les nombres ci-dessous 2³² et trouve le cent millionième premier (ici) en environ 1,1 secondes.

La voie rapide

Si nous voulons seulement trouver le n^TH prime, il n'y a pas valeur intrinsèque en trouvant également tous les nombres premiers plus petits. Si nous pouvons ignorer la plupart d'entre eux, nous permet d'économiser beaucoup de temps et de travail. Étant donné une bonne approximation a(n) à la n^th prime p(n), si nous avons un moyen rapide de calculer le nombre de nombres premiers π(a(n)) ne dépassant pas a(n), nous pouvons alors tamiser une petite plage au-dessus ou au-dessous de a(n) pour identifier les quelques nombres premiers manquants ou excédentaires entre a(n) et p(n).

Nous avons vu une approximation assez bonne facilement calculée pour p(n) ci-dessus, nous pourrions prendre

a(n) = n*(log n + log (log n))

Par exemple.

Une bonne méthode pour calculer π(x) est la méthode Meissel-Lehmer , qui calcule {[149] } en peu de temps O(x^0.7) (la complexité exacte dépend de l'implémentation, un raffinement par Lagarias, Miller, Odlyzko, Deléglise et Rivat permet de calculer π(x) en O (x^2/3 / log2 x) temps).

À partir de l'approximation simple a(n), nous calculons e(n) = π(a(n)) - n. Par le théorème des nombres premiers, la densité des nombres premiers près de a(n) est d'environ 1/log a(n), donc nous nous attendons à ce que p(n) soit proche de b(n) = a(n) - log a(n)*e(n) et nous tamiserions une plage légèrement plus grande que log a(n)*e(n). Pour une plus grande confiance que p(n) est dans la gamme tamisée, on peut augmenter la gamme par un facteur de 2, disons, qui sera presque certainement assez grand. Si la série semble trop grand, on peut itérer avec la meilleure approximation b(n) au lieu de a(n), calculer π(b(n)) et f(n) = π((b(n)) - n. En règle générale, |f(n)| sera beaucoup plus petit que |e(n)|. Si f(n) est d'environ -e(n), c(n) = (a(n) + b(n)) / 2 sera une meilleure approximation de p(n). Ce n'est que dans le cas très improbable où f(n) est très proche de e(n) (et pas très proche de 0), trouver une approximation suffisamment bonne à p(n) pour que l'étape finale de tamisage puisse être effectuée dans un temps comparable au calcul π(a(n)) devient un problème.

En général, après une ou deux améliorations à l'approximation initiale, la plage à tamiser est suffisamment petite pour que l'étape de tamisage ait un complexité de O (N^0.75) ou mieux.

Cette méthode trouve le cent millionième premier en environ 40 millisecondes, et le 10¹²-TH prime, 29996224275833, en moins de huit secondes.

---

TL; dr: trouver le n^th prime peut être efficacement fait, mais plus vous le voulez efficace, plus les mathématiques sont impliquées.

---

J'ai du code Java pour la plupart des algorithmes discutés préparés ici, au cas où quelqu'un veut jouer avec eux.

---

{[203]¹ 1 Remarque de côté pour les âmes désintéressées: la définition des nombres premiers utilisés dans les mathématiques modernes est différente, applicable dans des situations beaucoup plus générales. Si nous adaptons la définition de l'école pour inclure des nombres négatifs-donc un nombre est premier s'il n'est ni 1 ni -1 et divisible seulement par 1, -1, lui-même et son négatif - cela définit (pour les entiers) ce qu'on appelle aujourd'hui un élémentirréductible de ℤ, cependant, pour les entiers, les définitions des éléments premiers et irréductibles coïncident.