Función isPrime para lenguaje Python

Solución:

De muchas pruebas de números primos que flotan en 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 que n es:

1. no 2 o 3 (que son primos) y
2. ni siquiera (con n%2) y
3. no divisible por 3 (con n%3) entonces podemos probar cada 6 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*x La función solo tiene que recorrer 1 ciclo para encontrar que 5005 es divisible entre 5 y, por lo tanto, no es primo. Ya que 5 X 1001 == 1001 X 5 (y ambos son 5005), ¡no necesitamos ir hasta 1001 en el ciclo 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:

1. No prueba si n es menor que 2, y no hay primos menores que 2;
2. Prueba todos los números entre 2 y n ** 0.5, incluidos todos los números pares e impares. Dado que todo número mayor que 2 que es divisible por 2 no es primo, podemos acelerarlo un poco probando solo 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

De acuerdo, eso lo acelera en aproximadamente un 30% (lo comparé …)

El algoritmo que utilicé is_prime es aproximadamente 2 veces más rápido aún, ya que solo cada sexto entero pasa por 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á 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 verificar. Cuando lo divide por 4 y obtiene 5, sabe que es divisible tanto por 4 como por 5, sin tener que buscar 5.

Después de llegar a este punto medio en los factores, no tendrá más números para verificar que no haya reconocido anteriormente como factores. Por lo tanto, solo necesita ir a la mitad para ver si algo es primo, y este punto medio se puede encontrar tomando 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 teniendo 2 factores, 1 y él mismo. es decir, 2 es 1 * 2, 3 es 1 * 3, 5 es 1 * 5. Pero 1 (1 * 1) solo tiene 1 factor. Por lo tanto, no cumple con esta definición.

No se realizan operaciones de coma flotante a continuación. Esto es más rápido y tolerará argumentos más altos. La razón por la que debes ir solo a la raíz cuadrada es que si un número tiene un factor mayor que su raíz cuadrada, también tiene un factor menor que él.

def is_prime(n):
    """"pre-condition: n is a nonnegative integer
    post-condition: return True if n is prime and False otherwise."""
    if n < 2: 
         return False;
    if n % 2 == 0:             
         return n == 2  # return False
    k = 3
    while k*k <= n:
         if n % k == 0:
             return False
         k += 2
    return True

---

---

Utiliza Nuestro Buscador