Comment calculer le plus grand nombre premier plus petit que la valeur x?Algorithme pour trouver le plus grand nombre premier plus petit que x
En réalité, il n'est pas forcément exact, juste approximatif et proche de x.
x est un entier de 32 bits.
L'idée est que x est un paramètre de configuration. J'utilise le plus grand nombre premier moins de x (appelez-y y) comme le paramètre d'un constructeur de classe. La valeur y doit être un nombre premier.
Quelques bonnes informations here sur la fonction pi (x). Apparemment,
pi(x) = the number of primes less than x
et vous pouvez approcher pi (x) avec
x/(log x - 1)
tout
the n-th prime of that list of primes is equal to approximately n(log n)
Merci, c'est ce que je suis après. Assez proche lorsque vous calculez le nième – Matt
Gauss de Li (la [fonction intégrale logarithmique offset] (http://en.wikipedia.org/wiki/Logarithmic_integral_function)) est un bien meilleur estimateur que * x */(log * x * - 1) - Comme Chris Caldwell explique à la page liée! –
Wow, super réponse et super intéressant aussi! @GarethRees Je ne comprends pas ce qu'il veut dire par: > Et on peut voir de la même façon que la fonction Li (x) - (1/2) Li (x1/2) est «en moyenne» mieux approximation que Li (x) à pi (x); mais aucune importance ne peut être attachée à ces derniers termes dans la formule de Riemann, même par des moyennes répétées. –
À quelle vitesse vous avez besoin du programme fonctionne? Et à quelle fréquence calculez-vous ce problème?
Si vous avez besoin d'une réalisation rapide et ne vous souciez pas de la mémoire. Vous pouvez générer une table de début croissante par la méthode de tamisage puis la maintenir pendant la durée de vie du programme, puis quand vous trouvez le plus grand nombre premier plus petit que la valeur x, recherchez simplement le tableau et en O (log N) peut trouver une réponse exacte.
Pour de plus petites gammes de nombres premiers, c'est certainement le moyen le plus rapide de le faire. Tous les nombres premiers à deux octets (6542 d'entre eux) entreront dans un cache L1 de 16 Ko s'ils sont stockés en tant que valeurs 16 bits, et ils entreront dans un cache L1 de 32 Ko s'ils sont stockés en tant que valeurs 32 bits. Toutes les CPU récentes ont au moins un cache de données L1 de 32 ko. Les 1077871 nombres premiers qui peuvent être représentés avec 3 octets chacun ne seront pas tout à fait dans un cache L2 de 4 Mo s'ils sont stockés en tant que valeurs 32 bits, mais le feront si vous en emportez 5 en 16 octets, ce qui vous permet de faire une recherche binaire efficace . – user57368
Je pense que vous auriez peut-être besoin de connaître quelques nombres premiers contextuels pour mieux résoudre ce problème. Est-ce possible? X n'est pas premier? – marklar
A quelle échelle? Des entiers 32 bits? Ou pour cracher des standards tels que des nombres à 1024 bits? – selbie
x va être dans la gamme int32 – Matt