Existe-t-il une formule efficace qui peut aboutir au prochain (suivant) nombre premier ou le suivant ?

Article initialement publié sur Quora

Non, mais il existe:

1. des formules qui donnent des nombres premiers plus souvent qu’en tirant au hasard (ou en suivant) par exemple les nombres de la forme p=3×2^{n-1 ( Nombre de Thebit ) ou p = 2}n-1 où n est premier ( Nombre de Mersenne )
2. des méthodes très rapides pour savoir si ces “candidats” sont premiers ou non. Le Test de primalité de Miller-Rabin est le plus utilisé en pratique (= en cryptographie pour générer des clés)
3. avec ce qui précède, du code assz efficace comme Goulib.math2.nextprime ou Goulib.math2.random_prime

(voir Comment trouver des nombres premiers - Pourquoi Comment Combien )

En passant, il semblerait que les propriétés étonnantes des nombres premiers soient plus liées au principe de base du crible qu’à leur absence de diviseurs. Voir 2019 passée au crible - Pourquoi Comment Combien