Trouver la position du nombre premier

votre portée va seulement à dix millions, ce qui est petit pour ce genre de chose. J'ai deux suggestions:

1) Créer une table de pi(n) à intervalles commodes, puis utiliser un tamis segmenté D'Eratosthènes pour compter les nombres premiers entre les deux entrées de table qui encadrent la valeur désirée. La taille de l'intervalle détermine à la fois la taille du tableau requis et la vitesse à laquelle les résultats peuvent être calculés.

2) utiliser la fonction Phi(x,a) de Legendre et la fonction Lehmer le premier comptage formule pour calculer le résultat directement. La fonction phi nécessite un peu de stockage, Je ne suis pas sûr exactement combien.

parmi les deux, je choisirais probablement la première Solution compte tenu de la taille de votre problème. Implémentations des deux tamis segmenté D'Eratosthènes et Lehmer la fonction de comptage de prime est disponible sur mon blog.

EDIT 1:

à la réflexion, j'en ai une troisième alternative:

3) Utilisez l'intégrale logarithmique pour estimer pi(n). Il est monotone croissant, et toujours plus grand que pi(n) au cours de l'intervalle dont vous avez besoin. Mais les différences sont petites, jamais plus de 200. Donc vous pouvez précalculer les différences pour toutes les valeurs inférieures à dix millions, faire un tableau des 200 points de changement, puis quand demandé calculer l'intégrale logarithmique et chercher le facteur de correction dans le tableau. Ou vous pourriez faire quelque chose de similaire avec le R de Riemann fonction.

la troisième alternative prend le moins d'espace, mais je pense que l'espace requis pour la première alternative ne serait pas trop grand, et le tamisage est probablement plus rapide que le calcul de l'intégrale logarithmique. je vais donc m'en tenir à ma recommandation initiale. Il y a une implémentation de l'intégrale logarithmique et de la fonction R de Riemann à mon blog.

EDIT 2:

cela n'a pas très bien fonctionné, comme les commentaires indiquer. S'il vous plaît, ignorez ma troisième suggestion.

en guise de pénitence pour mon erreur en suggérant une solution qui ne fonctionne pas, j'ai écrit le programme qui utilise une table de valeurs de pi(n) et un tamis segmenté D'Eratosthènes pour calculer les valeurs de pi(N) pour n < 10000000. Je vais utiliser Python, plutôt que le C demandé par le poster original, parce que Python est plus simple et plus facile à lire à des fins pédagogiques.

nous commençons par calculer les nombres premiers de tamisage inférieurs au carré ces nombres premiers seront utilisés à la fois dans la construction de la table des valeurs de pi(n) et dans la réalisation du tamis qui calcule la réponse finale. La racine carrée de dix millions est 3162.3. Nous ne voulons pas utiliser 2 comme premier tamisage -- nous tamiserons seulement sur des nombres impairs, et traiterons 2 comme un cas spécial -- mais nous voulons que le premier suivant soit plus grand que la racine carrée, de sorte que la liste des premiers tamisage ne soit jamais épuisée (ce qui causerait une erreur). Nous utilisons donc cette version très simple du tamis de L'Ératosthène pour calculer les nombres premiers de tamisage:

def primes(n):
    b, p, ps = [True] * (n+1), 2, []
    for p in xrange(2, n+1):
        if b[p]:
            ps.append(p)
            for i in xrange(p, n+1, p):
                b[i] = False
    return ps

Le tamis D'Eratosthène fonctionne en deux parties. Tout d'abord, faites une liste des nombres inférieurs au nombre cible, à partir de 2. Ensuite, exécutez à plusieurs reprises à travers la liste, en commençant par le premier nombre non croisé, et barrez tous les multiples du nombre de la liste. Au départ, 2 est le premier nombre non croisé, donc rayez 4, 6, 8, 10, et ainsi de suite. Puis 3 est le prochain nombre non corrigé, donc rayez 6, 9, 12, 15, et ainsi de suite. Puis 4 a été rayé comme un multiple de 2, et le nombre suivant non rayé est 5, donc rayer 10, 15, 20, 25, et ainsi de suite. Continuer jusqu'à ce que tous les nombres non croisés aient été considérés; les nombres qui restent non croisés sont premiers. La boucle sur p considère chaque nombre à son tour, et si elle n'est pas croisée, la boucle sur i coupe les multiples.

primes la fonction retourne une liste de 447 nombres premiers: 2, 3, 5, 7, 11, 13, ..., 3121, 3137, 3163. Nous avons rayé 2 de la liste et stocké 446 tamisage nombres premiers dans la variable ps globale:

ps = primes(3163)[1:]

la fonction primaire dont nous aurons besoin compte les nombres premiers sur une plage. Il utilise un tamis que nous allons stocker dans un tableau global afin qu'il puisse être réutilisé au lieu d'être réattribué à chaque invocation de la fonction count:

sieve = [True] * 500

count fonction utilise une segmentation Crible d'Eratosthène pour compter les nombres premiers sur une plage de lo hi lo et hi sont tous deux inclus dans la gamme). La fonction a quatre for boucles: le premier efface le tamis, le dernier compte les nombres premiers, et les deux autres procèdent au tamisage, d'une manière similaire au tamis simple ci-dessus:

def count(lo, hi):
    for i in xrange(500):
        sieve[i] = True
    for p in ps:
        if p*p > hi: break
        q = (lo + p + 1) / -2 % p
        if lo+q+q+1 < p*p: q += p
        for j in xrange(q, 500, p):
            sieve[j] = False
    k = 0
    for i in xrange((hi - lo) // 2):
        if sieve[i]: k += 1
    return k

Le cœur de la fonction est la boucle for p in ps qui effectue le tamisage, en prenant chaque premier P de tamisage à tour de rôle. La boucle se termine lorsque le carré du premier tamisage est plus grand que la limite de la portée, puisque tous les nombres premiers seront identifiés à ce point (la raison pour laquelle nous avions besoin du premier suivant plus grand que le carré la racine est donc qu'il y aurait un premier tamisage pour arrêter la boucle). La variable mystérieuse q est l'offset dans le tamis du plus petit multiple de p dans la gamme lo à hi (notez qu'il n'est pas le plus petit multiple de p dans la gamme, mais l'indice de l'offset du plus petit multiple de p dans la gamme, ce qui peut prêter à confusion). if déclaration incréments de q quand il se réfère à un nombre qui est un carré parfait. Puis la boucle sur j frappe les multiples de p de la tamis.

Nous count fonction de deux façons. La première utilisation construit une table des valeurs de pi(n) à des multiples de 1000; la seconde utilisation interpole dans la table. Nous stockons la table dans une variable globale piTable:

piTable = [0] * 10000

nous choisissons les paramètres 1000 et 10000 sur la base de la requête originale pour maintenir l'utilisation de la mémoire à moins de cinquante kilooctets. (Oui, je sais que l'affiche originale détendu à cette exigence. Mais nous pouvons honorer de toute façon.) Dix mille entiers de 32 bits prendra 40,000 octets de stockage, et le tamisage sur une gamme de seulement 1000 de lo à hi exigera seulement 500 octets de stockage et sera très rapide. Vous voudrez peut-être essayer d'autres paramètres, pour voir comment ils affectent l'espace et le temps d'utilisation du programme. La construction de l' piTable est fait en appelant le count function dix mille fois:

for i in xrange(1, 10000):
    piTable[i] = piTable[i-1] + \
        count(1000 * (i-1), 1000 * i)

Tout le calcul jusqu'à ce point peut être fait au moment de la compilation au lieu de l'exécution. Quand j'ai fait ces calculs ideone.com, Ils ont pris environ cinq secondes, mais ce temps ne compte pas, parce qu'il peut être fait une fois pour toutes quand le programmeur écrit pour la première fois le code. En règle générale, vous devriez chercher des occasions de déplacer le code du temps d'exécution au temps de compilation, pour faire fonctionner vos programmes très rapidement.

La seule chose qui reste est d'écrire la fonction qui fait calcule le nombre de nombres premiers inférieurs ou égaux à n:

def pi(n):
    if type(n) != int and type(n) != long:
        raise TypeError('must be integer')
    if n < 2: return 0
    if n == 2: return 1
    i = n // 1000
    return piTable[i] + count(1000 * i, n+1)

Le premier if l'instruction fait la vérification de type. Le deuxième if l'énoncé renvoie une réponse correcte à une entrée ridicule. Le troisième if déclaration traite 2 spécialement; notre tamisage fait 1 un premier et 2 un composite, qui sont tous les deux incorrects, donc nous faisons la correction ici. Alors i est calculé comme le plus grand indice de piTable moins que le N demandé, et la déclaration de retour ajoute la valeur de piTable au compte de primes entre la valeur de table et la valeur demandée; la limite de hi est n+1, parce que sinon, dans le cas où n est premier, il ne serait pas compté. Par exemple, en disant:

print pi(6543223)

fera apparaître le numéro 447519 sur le terminal.

pi fonction est très rapide. ideone.com, mille aléatoire des appels à pi(n) ont été calculées en environ une demi-seconde, de sorte que la moitié environ une milliseconde de chacun; qui comprend le moment de générer le premier nombre et la somme du résultat, de sorte que le temps de calculer la fonction pi est même moins d'une demi-milliseconde. C'est un assez bon retour sur notre investissement dans la construction de la table.

si vous êtes intéressé par la programmation avec des nombres premiers, j'ai fait pas mal de travail sur mon blog. N'hésitez pas à venir visiter.