Check Prime Number

Q: Quelle est la complexité temporelle pour vérifier si un nombre est premier ?

La division par essais jusqu’à √n prend un temps de O(√n) et un espace de O(1) . Pour n jusqu’à 2^31-1 , cela représente au plus environ 46,000 divisions, ou 23,000 si l’on ignore les diviseurs pairs. Tester chaque diviseur jusqu’à n-1 est en O(n) , soit environ deux milliards d’étapes pour la plus grande entrée.

Q: Pourquoi ne vérifier que les diviseurs jusqu’à la racine carrée de n ?

Les diviseurs vont par paires d et n / d dont le produit est n . Si les deux étaient supérieurs à √n , leur produit serait supérieur à n . Ainsi, chaque paire contient un élément inférieur ou égal à √n , et si aucun diviseur n’apparaît jusque-là, n est premier.

Q: 1 est-il un nombre premier ?

Non. Un nombre premier a exactement deux diviseurs différents, 1 et lui-même, et 1 n’en a qu’un seul. Exclure 1 permet de garantir que la décomposition en facteurs premiers de chaque nombre entier est unique. C’est pourquoi isPrime(1) renvoie false .

Q: Existe-t-il un moyen plus rapide de tester si de très grands nombres sont premiers ?

Pour un nombre de 32 bits, la division par essais jusqu’à √n est suffisamment rapide. Pour les nombres de plusieurs dizaines de chiffres, les programmes utilisent le test de Miller-Rabin, qui vérifie quelques puissances modulaires au lieu d’essayer des diviseurs. Pour répertorier tous les nombres premiers jusqu’à une limite, le crible d’Ératosthène est plus efficace que de tester chaque nombre individuellement.

DébutantMaths et simulation

+10

Un nombre premier est un entier supérieur à 1 dont les seuls diviseurs sont 1 et lui-même. On vous donne un entier positif n. Retournez true si n est premier et false sinon. Le nombre 1 n’est pas premier.

Fonction

isPrime(n: integer) → boolean

ninteger: l’entier positif à tester
Renvoieboolean: vrai si n est premier, faux sinon

Contraintes

1 ≤ n ≤ 2³¹ - 1

Exemples

Entrée: n = 29
Sortie: true
Explication: Aucun de 2, 3, 4 ou 5 ne divise 29, et 6 × 6 = 36 dépasse déjà 29, donc il ne reste aucun diviseur à trouver. 29 est premier.

Entrée: n = 1
Sortie: false
Explication: Un nombre premier a exactement deux diviseurs, 1 et lui-même. 1 n’a qu’un seul diviseur, donc la réponse est false.

Entrée: n = 91
Sortie: false
Explication: 91 semble être un nombre premier, mais 7 × 13 = 91. Le diviseur 7 apparaît avant que la recherche ne dépasse √91 ≈ 9.5.

+15 tests cachés à la soumission

Pour aller plus loin

Tout nombre premier supérieur à 3 est de la forme 6k-1 ou 6k+1. Peux-tu utiliser cela pour ne tester qu’un tiers des diviseurs candidats ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La définition indique qu’il faut éliminer tous les diviseurs de 2 à n-1, ce qui représente plus de deux milliards de divisions pour la plus grande valeur première en entrée. Les diviseurs vont par paires dont le produit est égal à n, et le plus petit de chaque paire est inférieur ou égal à √n. Il suffit donc de chercher jusqu’à √n, soit au maximum environ 23,000 candidats impairs.

Essayez tous les diviseurs

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La définition te donne l’algorithme. Un nombre n ≥ 2 est premier lorsqu’aucun des nombres 2, 3, ..., n-1 ne le divise. Teste chaque candidat d avec n % d == 0 et renvoie false dès que l’un d’eux le divise. Pour 91, la boucle essaie les nombres de 2 à 6 et s’arrête à 7.

Traite d’abord le cas n < 2. Pour n = 1, l’ensemble des candidats est vide : la boucle ne trouverait donc jamais de diviseur et considérerait 1 comme un nombre premier.

Les nombres composés s’arrêtent généralement tôt, mais un nombre premier résiste à tous les tests : la boucle va donc jusqu’au bout. Pour n = 2147483647, qui est premier, cela représente environ 2.1 × 10^9 divisions, bien plus que ce que quelques secondes permettent.

Algorithme

Si n < 2, renvoie false.
Parcours d de 2 à n-1.
Si n % d == 0, renvoie false.
Après la boucle, renvoie true.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

Division par essais jusqu’à la racine carrée

Intuition

Les diviseurs vont par paires. Si d divise n, alors n / d le divise aussi, et les deux se multiplient pour donner n. Ils ne peuvent pas être tous deux supérieurs à √n, car leur produit serait alors supérieur à n. Ainsi, si n a un diviseur autre que 1 et lui-même, il en a un qui est inférieur ou égal à √n. Pour 91, la paire est 7 et 13, et 7 ≤ 9.5. Si aucun nombre jusqu'à √n ne divise n, aucun nombre supérieur ne le divise non plus.

Écrivez la borne sous la forme d * d ≤ n au lieu d'appeler une fonction racine carrée. Cela reste dans les nombres entiers, sans arrondi. Le signe égal est important : 49 = 7 × 7, et son seul diviseur 7 se trouve exactement à √49.

Vous pouvez aussi ignorer la moitié des candidats. Traitez 2 à part : un n pair est premier uniquement s'il vaut 2. Ensuite, un n impair n'a que des diviseurs impairs ; commencez donc à 3 et avancez de 2. Pour n = 2147483647, la boucle s'exécute alors environ 23,000 fois au lieu de 2.1 × 10^9.

Algorithme

Si n < 2, renvoie false.
Si n est pair, renvoie si n == 2.
Initialise d à 3 et boucle tant que d * d ≤ n, en utilisant un type 64 bits pour d.
Si n % d == 0, renvoie false. Sinon, ajoute 2 à d.
Après la boucle, renvoie true.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Pièges et cas limites

L’idée tient en une ligne. Les bogues se nichent aux limites : les plus petites entrées et le dernier diviseur.

Renvoyer true pour 1. Il a un seul diviseur, pas deux : il n’est donc pas premier.
Rejeter 2 parce qu’il est pair. Vérifie n == 2 avant d’écarter les nombres pairs.
Faire tourner la boucle tant que d * d < n au lieu de ≤. Les carrés de nombres premiers tels que 9, 49 et 2147117569 = 46337² sont alors considérés comme premiers.
Débordement dans d * d. Avec un int de 32 bits, 46341 × 46341 = 2147488281 ne tient pas et devient un nombre négatif : le test continue donc de réussir et la boucle va bien au-delà de √n. Utilise un type 64 bits pour d, ou compare plutôt d ≤ n / d.
Prendre la limite à partir d’un sqrt à virgule flottante et tronquer le résultat. Un double est exact pour toutes les valeurs de n ici, mais pour les entrées sur 64 bits, l’arrondi peut donner une valeur inférieure d’une unité à la vraie racine et faire sauter le seul diviseur important. d * d ≤ n ne présente pas ce risque.

Questions fréquentes4

Quelle est la complexité temporelle pour vérifier si un nombre est premier ?

La division par essais jusqu’à √n prend un temps de O(√n) et un espace de O(1). Pour n jusqu’à 2^31-1, cela représente au plus environ 46,000 divisions, ou 23,000 si l’on ignore les diviseurs pairs. Tester chaque diviseur jusqu’à n-1 est en O(n), soit environ deux milliards d’étapes pour la plus grande entrée.

Pourquoi ne vérifier que les diviseurs jusqu’à la racine carrée de n ?

Les diviseurs vont par paires d et n / d dont le produit est n. Si les deux étaient supérieurs à √n, leur produit serait supérieur à n. Ainsi, chaque paire contient un élément inférieur ou égal à √n, et si aucun diviseur n’apparaît jusque-là, n est premier.

1 est-il un nombre premier ?

Non. Un nombre premier a exactement deux diviseurs différents, 1 et lui-même, et 1 n’en a qu’un seul. Exclure 1 permet de garantir que la décomposition en facteurs premiers de chaque nombre entier est unique. C’est pourquoi isPrime(1) renvoie false.

Existe-t-il un moyen plus rapide de tester si de très grands nombres sont premiers ?

Pour un nombre de 32 bits, la division par essais jusqu’à √n est suffisamment rapide. Pour les nombres de plusieurs dizaines de chiffres, les programmes utilisent le test de Miller-Rabin, qui vérifie quelques puissances modulaires au lieu d’essayer des diviseurs. Pour répertorier tous les nombres premiers jusqu’à une limite, le crible d’Ératosthène est plus efficace que de tester chaque nombre individuellement.

Python

def isPrime(n):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

n = 29

Attendu

true