Vérifier si un nombre est premier - un peu plus rapide
Supposons qu’un programme qui vérifie si un nombre est premier soit déjà utilisé en production par une grande entreprise. Cependant, à mesure que l’entreprise se développe rapidement et que le nombre d’utilisateurs augmente, le nombre de requêtes adressées à votre code augmente également. L’entreprise vous demande donc d’optimiser ce programme pour qu’il s’exécute un peu plus vite et puisse gérer l’afflux massif de nouveaux utilisateurs.
Votre solution précédente consistait probablement à :
- Parcourir les nombres de 2 jusqu’à
npour compter le nombre de diviseurs.
- Parcourir les nombres de 2 jusqu’à
net s’arrêter dès qu’un diviseur était trouvé.
Il existe plusieurs petites optimisations que nous pouvons apporter :
Optimisation 1 :
Au lieu de tester tous les nombres de 2 à
n, nous pouvons vérifier d’abord si n est divisible par 2, puis ne tester que les nombres impairs. Si n n’est pas divisible par 2, alors il est inutile de vérifier tous les autres nombres pairs plus grands (4, 6, 8, 10, 12, etc.).Optimisation 2 :
Au lieu de parcourir de 2 jusqu’à
n, nous pouvons nous limiter à n/2, car le plus petit diviseur possible est 2 ⇒ nous ne trouverons aucun diviseur plus grand que n/2.Nous pouvons combiner les optimisations 1 et 2. Ainsi, les candidats seront uniquement les nombres impairs jusqu’à
n/2. Il y a environ n/4 de ces nombres, donc cette approche est quatre fois plus efficace qu’un simple test linéaire.Ces optimisations rendent le code un peu plus rapide, mais en termes de complexité, l’algorithme effectue toujours une recherche linéaire de diviseurs. Ainsi, lorsque
n grandit, l’algorithme effectue proportionnellement plus d’opérations. Nous verrons plus tard comment optimiser drastiquement la vérification de primalité pour éviter que la charge de travail augmente proportionnellement à n.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ).Sortie
Le programme doit afficher
Yes si n est premier et No dans le cas contraire.Exemples
Input | Output |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB