Algoritmo de verificación principal de Python
Comprueba si un número es primo usando Python. Ejecute nuestro algoritmo interactivo para ver una iteración matemática y una evaluación de raíces eficientes.
Descripción general
Un número primo es un entero positivo mayor que 1 que no tiene divisores positivos distintos de 1 y él mismo.
La forma más ineficaz de comprobar si hay un número primo es iterar hasta el número mismo. Una optimización poderosa es verificar solo la divisibilidad hasta la raíz cuadrada del número.
Código y salida de ejecución
Algoritmo eficiente de verificación de primos que demuestra la optimización 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 -> PrimeImplementación paso a paso
- Algoritmos de criptografía y hash
- Matemáticas educativas y teoría del tamiz.
- Validación de backend para claves seguras
Preguntas frecuentes
¿Por qué comprobar sólo hasta la raíz cuadrada?
Si $n = a \times b$, entonces al menos uno de los factores ($a$ o $b$) debe ser menor o igual a la raíz cuadrada de $n$. Por lo tanto, comprobar más es redundante.
Temas relacionados
Ejecute y comprenda la secuencia de Fibonacci en Python. Este ejemplo de código interactivo muestra enfoques iterativos y recursivos para generar números de Fibonacci.
Algoritmos de clasificación de PythonExplore los algoritmos de clasificación de Python. Visualice la clasificación por burbujas y la clasificación por combinación de forma nativa dentro del contexto IDE de un navegador.