Trouver la position du nombre premier

je dois faire l'inverse de trouver le nième prime, i.e. à partir d'un nombre premier, je dois trouver sa position en

2, 3, 5, 7...

le nombre premier peut être grand, dans l'ordre de 10^7. Aussi, il ya beaucoup d'entre eux.

j'ai un index de nombres premiers pré-calculés qui peuvent être binaires-recherchés, mais j'ai aussi une limite d'espace de 50k! Peut tamis être fait? Ou de tout autre moyen rapide?

EDIT: Merci beaucoup pour toutes les réponses brillantes, Je n'étais pas attendez! J'espère qu'ils sont utiles à d'autres personnes qui cherchent la même chose.

13
demandé sur Max 2013-01-02 22:07:42

7 réponses

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.

8
répondu user448810 2013-01-07 20:13:37

si vous savez a priori que l'entrée est prime, vous pouvez utiliser l'approximation pi(n) ≈ n / log n avec un petit tableau de fixups pour les primes où arrondir le résultat n'est pas suffisant pour obtenir la valeur correcte N. Je pense que c'est votre meilleur pari dans le cadre de la contrainte de taille, mis à part une approche lente de la force brute.

4
répondu R.. 2013-01-02 18:41:02

je suggère qu'un modèle hybride heuristique fonctionne ici. Stockez chaque nième prime, puis faites une recherche linéaire via les tests de primalité. Pour accélérer les choses, vous pouvez utiliser un test de primalité simple et rapide (comme le test de Fermat avec a==2) et précalculer les faux positifs. Certains ajustements en fonction de la taille maximale de l'entrée et vos contraintes de stockage doit être facile à travailler.

3
répondu user295691 2013-01-02 18:32:57

Voici un code qui fonctionne. Vous devriez remplacer le test de primalité basé sur la division de première instance par un test déterministe Miller-Rabin test qui fonctionne pour votre plage d'entrée. Tamiser pour trouver des nombres premiers dans la petite gamme appropriée fonctionnerait mieux que la division de première instance, mais c'est un pas dans la mauvaise direction.

#include <stdio.h>
#include <bitset>
using namespace std;

short smallprimes[549]; // about 1100 bytes
char in[19531]; // almost 20k

// Replace me with Miller-Rabin using 2, 7, and 61.
int isprime(int j) {
 if (j<3) return j==2;
 for (int i = 0; i < 549; i++) {
  int p = smallprimes[i];
  if (p*p > j) break;
  if (!(j%p)) return 0;
 }
 return 1;
}

void init() {
 bitset<4000> siv;
 for (int i = 2; i < 64; i++) if (!siv[i])
  for (int j = i+i; j < 4000; j+=i) siv[j] = 1;
 int k = 0;
 for (int i = 3; i < 4000; i+=2) if (!siv[i]) {
  smallprimes[k++] = i;
 }

 for (int a0 = 0; a0 < 10000000; a0 += 512) {
  in[a0/512] = !a0;
  for (int j = a0+1; j < a0+512; j+=2)
   in[a0/512] += isprime(j);
 }
}

int whichprime(int k) {
 if (k==2) return 1;
 int a = k/512;
 int ans = 1 + !a;
 for (int i = 0; i < a; i++) ans += in[i];
 for (int i = a*512+1; i<k; i+=2) ans += isprime(i);
 return ans;
}

int main() {
 int k;
 init();
 while (1 == scanf("%i", &k)) printf("%i\n", whichprime(k));
}
2
répondu tmyklebu 2013-01-02 19:44:02

La suite ressemble à ce que vous recherchez. http://www.geekviewpoint.com/java/numbers/index_of_prime. Vous y trouverez le code et les tests unitaires. Depuis votre liste est relativement faible (c'est à dire 10^7), il devrait le gérer.

en gros vous trouvez tous les nombres premiers entre 2 et n puis compter tous les nombres premiers moins que n pour trouver l'index. Aussi, dans le cas où n n'est pas premier, la fonction renvoie -1.

1
répondu Konsol Labapen 2013-01-02 20:13:39

j'ai fait exactement cela une fois. A écrit un code, celui donné n, peut trouver rapidement le nième premier, jusqu'à n = 203542528, donc environ 2e8. Ou, il peut revenir en arrière, pour tout nombre n peut dire combien de nombres premiers sont inférieurs à n.

Une base de données est utilisé. Je stocke tous les nombres premiers jusqu'à un certain point (le sqrt de ma limite supérieure. Dans votre cas, cela signifie que vous stockerez tous les nombres premiers jusqu'à sqrt(1e7). Il y a 446, vous pouvez stocker la liste sous forme compressée, puisque le maximum jusqu'à présent, la différence n'est que de 34. Au-delà de ce point, stockez chaque KTH prime (pour une certaine valeur de K.) Puis un tamis rapide est suffisant pour générer tous les nombres premiers dans un court intervalle.

donc dans MATLAB, pour trouver le 1E7'th prime:

nthprime(1e7)
ans =
   179424673

Ou bien, il peut trouver le nombre de nombres premiers inférieurs que 1e7:

nthprime(1e7,1)
ans =
      664579

le fait est, une telle base de données est facile à construire et à rechercher. Si votre base de données peut être pas plus de 50, il devrait y avoir aucun problème.

0
répondu 2013-01-03 00:50:49

Ce que vous suggérez est le meilleur. Pré-calculer (ou télécharger) la liste des nombres premiers inférieurs à 10^7, puis recherche binaire.

il n'y a que 664579 nombres premiers de moins de 10^7, donc la liste consommera ~2,7 MB d'espace. La recherche binaire pour résoudre chaque instance sera super speedy-seulement ~20 opérations.

0
répondu Colonel Panic 2013-01-03 10:18:46