Algorithme Python Prime Checker
Vérifiez si un nombre est premier en utilisant Python. Exécutez notre algorithme interactif pour voir une itération mathématique et une évaluation racine efficaces.
Aperçu
Un nombre premier est un entier positif supérieur à 1 qui n'a pas de diviseur positif autre que 1 et lui-même.
La manière la plus inefficace de rechercher un nombre premier consiste à itérer jusqu'au nombre lui-même. Une optimisation puissante consiste à vérifier uniquement la divisibilité jusqu'à la racine carrée du nombre.
Sortie de code et d'exécution
Algorithme de vérification des primes efficace démontrant l’optimisation O(sqrt(n)).
import math
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
max_divisor = math.isqrt(n)
for i in range(3, max_divisor + 1, 2):
if n % i == 0:
return False
return True
test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
status = "Prime" if is_prime(num) else "Not Prime"
print(f"{num:2d} -> {status}") 2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> PrimeMise en œuvre étape par étape
- Algorithmes de cryptographie et de hachage
- Mathématiques pédagogiques et théorie du tamis
- Validation backend pour les clés sécurisées
Foire aux questions
Pourquoi vérifier seulement jusqu'à la racine carrée ?
Si $n = a \times b$, alors au moins un des facteurs ($a$ ou $b$) doit être inférieur ou égal à la racine carrée de $n$. Ainsi, vérifier plus haut est redondant.
Sujets connexes
Exécutez et comprenez la séquence de Fibonacci en Python. Cet exemple de code interactif montre des approches itératives et récursives pour générer des nombres de Fibonacci.
Algorithmes de tri PythonExplorez les algorithmes de tri Python. Visualisez le tri par bulles et le tri par fusion de manière native dans un contexte IDE de navigateur.