Algorithme rapide pour rechercher le nombre de nombres premiers entre deux nombres
Mon problème se réduit à trouver le nombre de nombres premiers entre deux nombres donnés.Je pourrait avoir une portée aussi grande que 1 to (1000)!
et donc je suis besoin de certains mathématique des optimisations.
Clairement le tamis méthode serait trop lent dans ce cas. Est-il mathématique d'optimisation qui peuvent être appliquées, comme par exemple, en prenant une petite partie de ce grand espace et de faire des inférences sur le reste des numéros.
P. S: Cela ressemble fort à je risque d'avoir atteint une impasse - mais tout ce que je suis à la recherche de quelques optimisations qui pourraient aider à résoudre ce problème. Et aussi, je suis seulement à la recherche d'une approche monothread.
EDIT: Une approche que j'ai pensé et peut résoudre beaucoup de grand nombre de problèmes liés - pour quelqu'un de maintenir un tableau global des nombres premiers et de la rendre disponible pour la recherche. Les gens à la PrimeGrid projet peut contribuer utilement à cette fin.
Poster du code, ou au moins certains Pseudo-code de quelques approches que vous avez essayé.
Sont les chiffres donnés entre 1 et
10^5
? Ou peuvent-ils beaucoup plus grande et c'est la longueur de l'intervalle qui peut être jusqu'à 10^5
?Les nombres donnés sont entre 1 et N, où N est autour de 1000!.
Si vous choisissez un N assez petit tel que une liste de tous les nombres premiers <= N peut être stocké sur un disque dur, alors il serait plus rapide de calculer tous ces nombres premiers à la volée plutôt que de les lire à partir du disque dur.
OriginalL'auteur Hari | 2012-01-20
Vous devez vous connecter pour publier un commentaire.
Puisque vous voulez aller aussi haut que
1000!
(factorielle). Vous ne serez pas en mesure d'obtenir des résultats exacts avec les méthodes connues sur les technologies actuelles.La Le Premier Comptage En Fonction a été évaluée exactement pour une poignée de valeurs jusqu'à
10^24
. Donc aucun moyen que vous serez en mesure de frapper1000!
.Mais puisque vous mentionnez qu'une approximation peut être fine, vous pouvez utiliser le Intégrale Logarithme comme une approximation du Premier Comptage en Fonction.
Ceci est basé sur la Théorème Des Nombres Premiers qui dit que le Premier Fonction de Comptage est asymptotique à l'Intégrale logarithme.
OriginalL'auteur Mysticial
Il y a un rapide, simple rapprochement pour le nombre de nombres premiers-dessous d'un certain lié. Si vous n'avez pas besoin des valeurs exactes, alors une différence de deux évaluations de cette formule, vous obtiendrez près.
OriginalL'auteur phs
La méthode la plus rapide que je connaisse serait d'éliminer tous les non-nombres premiers (même numéros, tous les numéros avec divisers plus faible que le nombre de départ à la plage, etc) aussi vite que vous pouvez, puis itérer sur les autres et d'utiliser quelque chose comme la Algorithme d'euclide pour déterminer si un nombre est un nombre premier.
Ah, c'est vrai. Je n'avais jamais entendu parler du crible de la méthode. Pourquoi en serait-il trop lent?
rien effectuée sur 100! est trop lent.
"utiliser l'algorithme d'Euclide pour calculer le PGCD d'un nombre donné avec? Tous les numéros ci-dessous sqrt(1000!) (== 79.26*367.88**500 = 5.6469*10^1284 ou quelque chose) ?
OriginalL'auteur joe_coolish
Vous pouvez étudier vos options ici:
http://en.wikipedia.org/wiki/Prime_counting_function
Cela ressemble aussi utile:
http://mathworld.wolfram.com/PrimeCountingFunction.html
Je demander pourquoi vous en avez besoin, jusqu'à 1000! ? On dirait que personne n'a jamais compté que beaucoup avant. Il y a 1,925,320,391,606,803,968,923 nombres premiers de 1-10^23. 1000! = 10^120. Je suis curieux maintenant.
Vous avez raison; Essayer de me souvenir comment je suis arrivé à mon erreur de calcul--mais la nuit dernière est floue
OriginalL'auteur bweaver
Le premier comptage algorithme développé par Lagarias et autres, cité par d'autres, fonctionne très grossièrement en O (n^(2/3)). Depuis un tamis pour les nombres premiers de k1 à k2 prend environ O (max (sqrt (k2), k2 - k1), vous devriez vérifier dans quelle mesure vos limites inférieure et supérieure sont séparés et soit faire un tamis ou utiliser le premier algorithme de comptage, selon ce qui sera plus rapide.
BTW. Le premier algorithme de comptage peut être accordé à compter les nombres premiers de 1 à n pour différentes valeurs de n qui sont assez proches plus rapide que de compter individuellement. (En gros, il choisit un nombre N, crée un tamis de taille n /N, et recherche N^2 valeurs dans ce tamis. Le O (n^(2/3)) vient du fait que pour N = n^(1/3) les deux opérations de N^(2/3) des mesures. Que les tamis peuvent être réutilisés pour différentes n, mais des valeurs différentes ont besoin d'être regardé. Donc, pour k différentes valeurs de n, de vous faire N un peu plus petit, ce qui augmente le coût du tamis (une seule fois), mais en réduisant le coût de la recherche (k fois)).
Pour n autour de 1000!, il n'y a aucune chance. Vous pouvez même pas compter le nombre de nombres premiers dans [n, n] pour des valeurs de cette taille si n n'a pas de petit(ish) facteurs.
OriginalL'auteur gnasher729