Vérifier si un nombre est premier - méthode rapide
Jusqu’ici, pour savoir si un nombre
n est premier, on utilisait essentiellement une recherche linéaire de ses diviseurs. Cela signifie que si l’on augmente n, le nombre d’opérations nécessaires pour déterminer la primalité de n augmente proportionnellement (selon un certain coefficient). Ainsi, dans les cas les plus défavorables (par exemple lorsque le nombre n est vraiment premier – 51, 107, etc.), notre algorithme effectuait environ n/4 opérations pour vérifier que n est premier.En conséquence, si on multiplie
n par 10, l’algorithme fait 10 fois plus d’opérations. Et si on multiplie n par 100, il exécute 100 fois plus d’opérations. Autrement dit, cet algorithme travaille en temps proportionnel à n. Peut-on faire mieux ? Il semble qu’une part importante de ces vérifications soit redondante.L’approche basée sur :
Supposons que
n possède un diviseur d.Cela veut dire que
n est divisible par d et que d, tout comme , sont des entiers. De plus, soit d, soit , est inférieur ou égal à . Ainsi, pour savoir si n est premier, il suffit de tester les nombres jusqu’à plutôt que jusqu’à . En effet, on ne s’intéresse qu’à vérifier si n est divisible par autre chose que 1 ou n, donc il suffit de tester le plus petit entre d et . L’un ou l’autre étant inévitablement plus petit ou égal à , on peut donc s’arrêter à .C’est une amélioration considérable ! Effectuer opérations au lieu de
n fait une énorme différence. Imaginez un algorithme qui aurait besoin de 10 ans (3650 jours) pour s’exécuter. S’il est optimisé pour ne traiter que opérations plutôt que n, il ne lui faudrait plus que 2 mois (61 jours) pour terminer.Existe-t-il de meilleurs algorithmes pour vérifier la primalité d’un nombre ?
Oui ! Vous pouvez en savoir plus en consultant Algorithms for Competitive Programming. Il existe des algorithmes dont le nombre d’opérations croît de façon logarithmique plutôt que proportionnelle à .
Entrée
La première ligne de l'entrée contient un seul entier
n (1 ≤ n ≤ ).Sortie
Le programme doit imprimer
Yes si n est premier et No sinon.Exemples
Input | Output |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB