Problème
Un nombre premier est un entier strictement supérieur à 1 qui n'est divisible que par 1 et lui-même. Il suffit de vérifier les diviseurs jusqu'à la racine carrée de n.
Implémentez is_prime(n).
Entrée
n : Le nombre à tester.
Sortie
Retournez true si n est premier, sinon false.
Contraintes
-1 000 ≤ n ≤ 1 000 000 000 000
Exemples
Entrée :
n = 29
Sortie attendue :
expected = TrueEntrée :
long long n = 29;
Sortie attendue :
bool expected = true;Entrée :
long n = 29;
Sortie attendue :
bool expected = true;Explication
29 n'a pas de diviseur autre que 1 et 29.
Entrée :
n = 21
Sortie attendue :
expected = FalseEntrée :
long long n = 21;
Sortie attendue :
bool expected = false;Entrée :
long n = 21;
Sortie attendue :
bool expected = false;Explication
21 = 3 × 7, donc ce n'est pas un nombre premier.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Traitez d’abord les nombres inférieurs à 2 ; ils ne peuvent pas être premiers.
Indice 2
Testez les diviseurs possibles seulement jusqu’à la racine carrée du nombre.
Indice 3
Faites attention aux nombres pairs et aux facteurs répétés : un seul diviseur suffit à invalider la primalité.
Complexité attendue
temps O(sqrt(n)), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.