Si vous avez passé du temps sur les guerres de codes, trouver si un nombre est premier est un thème commun parmi une catégorie de problèmes. Quand j’ai commencé à coder, je pensais que parcourir tous les nombres de 1 à num et vérifier s’il était divisible était une excellente approche. Cependant, dès que j’ai appris la notation big O, j’ai été mortifié!

Après quelques recherches et une lecture du wiki ce week-end, j’ai trouvé une excellente fonction pour trouver si un nombre est premier avec un temps O(n) sous-linéaire. La fonction suivante est la solution que j’ai trouvée:

function isPrime (num) {
if (num <= 1) {
return true
} else if (num <= 3) {
return true
} else if (num%2 === 0 || num%3 === 0) {
return false
}
let i = 5
while (i*i <= num) {
if (num%i === 0 || num%(i+2) === 0) {
return false
}
i += 6
}
return true
}
  1. Vérifie si le nombre est 0, 1 ou négatif. Renvoie true si le nombre se trouve dans cette plage.
  2. Vérifie si le nombre est 2 ou 3. Renvoyant true si le nombre est 2 ou 3.
  3. La dernière instruction if renvoie que le nombre n’est pas premier s’il est divisible par 2 ou 3.
  4. La dernière partie de cette fonction est la plus délicate — la boucle while ! Il vérifie essentiellement chaque nombre impair qui n’est pas divisible par 3 jusqu’à ce qu’il devienne plus grand que la racine carrée du nombre. Par exemple, les premiers i et i + 2 seront 5 et 7. Les i et i + 2 suivants seront 11 et 13. Il ne vérifie pas 9 ou 15 car les deux sont divisibles par 3 et auraient été capturés dans la dernière instruction else if.
  5. Renvoie enfin true si le nombre n’était divisible par aucune entrée i ou i+2 car le nombre est premier.

O(n)

Si nous supposons que n est le nombre passé dans isPrime, le O(n) de mon approche initiale serait O(n). Par conséquent, cette complexité temporelle serait linéaire. C’est bien si tout ce que vous faites est la vérification, mais plusieurs fois cette fonction est une fonction d’assistance et vérifier si une liste de nombres est première serait exponentielle.

La fonction ci-dessus isPrime serait O(n^1/2). Cela signifie que la complexité temporelle sera sous-linéaire, ce qui diminuera considérablement la complexité temporelle d’une fonction plus grande.

En Conclusion