(20 grands énumérant chiffres des nombres premiers) [probables]

Question

Compte tenu A, de l'ordre de 10 ^ 20, je voudrais obtenir rapidement une liste des premiers nombres premiers plus que A. OK, mes besoins ne sont pas tout à fait exact que - il est bien si de temps en temps un composite numéro se termine sur la liste.

Quelle est la façon la plus rapide d'énumérer la (probable) nombres premiers supérieur à A?

Y at-il un moyen plus rapide que tous les pas à pas dans les nombres entiers supérieurs à A (autres que des multiples évidentes de dire, 2 et 3) et effectuer un test de primalité pour chacun d'eux? Dans le cas contraire, et la seule méthode consiste à tester chaque entier, ce test de primalité dois-je utiliser?

Answer 1

Grande question. Ce n'est pas encore avéré être en temps polynomial (polynôme du nombre de chiffres, ici 20) - ce fut le le projet de Finding polymath nombres premiers, où plusieurs mathématiciens (y compris les champs médaillés Terence Tao et Tim Gowers!) ont essayé de trouver un algorithme, mais le projet ne semble pas avoir encore eu de résultats concrets .

Quoi qu'il en soit, il y a plusieurs choses que vous pouvez faire. L'un d'eux, comme vous et d'autres ont souligné, est essayer chaque numéro et vérifier si elle est premier, avec un test de primalité rapide comme Miller-Rabin . Heuristiques théorie des nombres bien connus (sur la base des nombre premier ), la « probabilité "à proximité d'un certain nombre n étant prime est d'environ 1 / ln (n), donc avec 10 ^ 20, à propos de tous les 46 numéros sera premier. Donc, si vous voulez k numéros à 20 chiffres, vous exécutez le test de Miller-Rabin sur environ 50k chiffres.

La seconde approche, que je pense pourrait être plus rapide si vous faites cela pour beaucoup beaucoup A ce (n'ont pas soigneusement pensé) est d'utiliser à la place un tamis , comme le Sieve de Eratosthène. Si vous voulez k nombres premiers, faire un tableau avec environ 50k numéros (ou plus pour être sûr), et tamiser à travers eux. Vous souhaitez commencer une liste précalculée des nombres premiers inférieurs un nombre. (10 ¹⁰ pour être tout à fait correct, mais puisque vous êtes prêt à tolérer certains nombres composés, une petite liste des nombres premiers feront, par exemple les tests par trouve le prochain nombre premier ou trouve les dix nombres premiers . Si vous l'utilisez en ligne, il semble que vous devrez les copier vers le bas à la main, mais le le code source est également disponible.

Answer 2

  

Y at-il un moyen plus rapide que le renforcement   à travers l'ensemble des nombres entiers supérieurs   que A (autres que des multiples évidentes   de dire, 2 et 3) et l'exécution d'une   test de primalité pour chacun d'eux?

Non, il n'y a aucun moyen de savoir si un nombre est premier sans test de primalité.

Vous pouvez cependant effectuer un test de primalité probabiliste, comme Miller-Rabin sur un nombre très rapidement. Ceci est une méthode sûre et bien accepté de trouver de grands nombres premiers. Depuis les nombres premiers sont relativement abondants, vous aurez aucun mal à trouver des nombres premiers dans une plage en utilisant cette méthode. Il suffit d'utiliser un test efficace et la mise en œuvre Miller-Rabin, et vous serez bien.

Answer 3

À propos du mieux que vous pouvez faire est de générer un candidat raisonnable, puis le tester. Le test de Miller-Rabin répond à vos besoins de donner une forte probabilité du nombre étant le premier, et vous pouvez réduire le risque d'un composite glisser à travers un niveau plus ou moins arbitraire en fonction du nombre d'itérations que vous utilisez.

Answer 4

sont des nombres fréquents nombres premiers calme. Fréquence des nombres premiers est log (n) qui signifie qu'en moyenne, chaque numéro est 46e premier où n = 10 ^ 20. Cela signifie que la vérification de chaque numéro pour primalité n'est pas de frais généraux.