Función isPrime para el lenguaje Python
Entonces pude resolver este problema con un poco de ayuda de Internet y esto es lo que obtuve:
def isPrime(n):
for i in range(2,int(n**0.5)+1):
if n%i==0:
return False
return True
Pero mi pregunta realmente es cómo hacerlo, pero ¿POR QUÉ? Entiendo que 1 no se considera un número "primo" aunque lo sea, y entiendo que si se divide por CUALQUIER COSA dentro del rango, automáticamente no es un número primo, por lo que devuelve la declaración Falso. pero mi pregunta es ¿qué papel juega aquí la raíz cuadrada de la "n" ?
PD: Soy muy inexperto y acabo de iniciarme en la programación hace un mes.
De muchas pruebas de números primos que circulan por Internet, considere la siguiente función de Python:
def is_prime(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
r = int(n**0.5)
# since all primes > 3 are of the form 6n ± 1
# start with f=5 (which is prime)
# and test f, f+2 for being prime
# then loop by 6.
f = 5
while f <= r:
print('\t',f)
if n % f == 0: return False
if n % (f+2) == 0: return False
f += 6
return True
Dado que todos los primos > 3 son de la forma 6n ± 1, una vez que eliminamos eso nes:
- no 2 o 3 (que son primos) y
- ni siquiera (con
n%2) y - no es divisible por 3 (con
n%3), entonces podemos probar cada sexto n ± 1.
Considere el número primo 5003:
print is_prime(5003)
Huellas dactilares:
5
11
17
23
29
35
41
47
53
59
65
True
La línea r = int(n**0.5)se evalúa como 70 (la raíz cuadrada de 5003 es 70,7318881411 y int()trunca este valor)
Considere el siguiente número impar (ya que todos los números pares distintos de 2 no son primos) de 5005, se imprime lo mismo:
5
False
El límite es la raíz cuadrada ya que x*y == y*xla función solo tiene que hacer 1 bucle para encontrar que 5005 es divisible por 5 y por lo tanto no es primo. Dado que 5 X 1001 == 1001 X 5(y ambos son 5005), no necesitamos llegar hasta 1001 en el bucle para saber lo que sabemos en 5.
Ahora, veamos el algoritmo que tienes:
def isPrime(n):
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
Hay dos cuestiones:
- No prueba si
nes menor que 2 y si no hay números primos menores que 2; - Prueba todos los números entre 2 y n**0,5, incluidos todos los números pares e impares. Dado que cada número mayor que 2 que es divisible por 2 no es primo, podemos acelerarlo un poco probando solo los números impares mayores que 2.
Entonces:
def isPrime2(n):
if n==2 or n==3: return True
if n%2==0 or n<2: return False
for i in range(3, int(n**0.5)+1, 2): # only odd numbers
if n%i==0:
return False
return True
OK, eso lo acelera en aproximadamente un 30% (lo comparé...)
El algoritmo que utilicé is_primees aproximadamente 2 veces más rápido aún, ya que solo uno de cada seis enteros recorre el bucle. (Una vez más, lo comparé).
Nota al margen: x**0,5 es la raíz cuadrada:
>>> import math
>>> math.sqrt(100)==100**0.5
True
Nota al margen 2: las pruebas de primalidad son un problema interesante en informática.
Con n**.5, no estás elevando n al cuadrado, sino sacando la raíz cuadrada.
Considere el número 20; los factores enteros son 1, 2, 4, 5, 10 y 20. Cuando divides 20 entre 2 y obtienes 10, sabes que también es divisible por 10, sin tener que comprobarlo. Cuando lo divides por 4 y obtienes 5, sabes que es divisible por 4 y 5, sin tener que comprobar si es 5.
Después de llegar a este punto medio en los factores, no tendrá más números para verificar que no haya reconocido como factores anteriormente. Por lo tanto, sólo necesitas llegar hasta la mitad para ver si algo es primo, y este punto medio se puede encontrar sacando la raíz cuadrada del número.
Además, la razón por la que 1 no es un número primo es porque los números primos se definen como si tuvieran 2 factores, 1 y él mismo. es decir, 2 es 1*2, 3 es 1*3, 5 es 1*5. Pero 1 (1*1) sólo tiene 1 factor, él mismo. Por lo tanto, no cumple con esta definición.
