Obtener numeros primos con Python
Un número primo es cualquier número mayor que 1 que tiene únicamente dos divisores: él mismo y el 1. Que sean divisiores quiere decir que se puede divir por ese numero y que no me sobre nada, que el resto sea 0.
Por lo tanto, si quisieramos saber si 24 es un número primero, un primer código buscaría recorrer todos los numeros menores a 24 para chequear que alguno de ellos sea divisor de 24. Pero no tiene sentido ir por todos los numeros menores de 24 para eso se utiliza la raiz cuadrada (math.sqrt) + 1.
Recordemos que para obtener el resto de una division con python se utiliza el operador % .
import math
def isPrime(num):
if num < 2:
return False
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
return False
return True
Ahora bien, hay un algoritmo un poco más complicado pero que es más rapido para encontrar números primos. Es el algoritmo de Eratóstenes, que comúnmente se lo conoce como el tamiz o criba de Eratóstenes. La clave de este algoritmo es descartar de antemano los multiplos de un número. Por ejemplo. si el 2 es primo, todos sus múltiplos no lo serán porque son divisibles por 2. De manera que 4, 6, 8, 10, 12, etc todos los números de la tabla del 2 que se pueden divivir por 1, por si mismos y también por 2; por lo tanto no son primos y podemos descartarlos. Del mismo modo con el 3, 3 es primo pero todos sus multiplos no lo són.
Aquí el algoritmo y luego una explicación de algunas lineas:
import math
def primeSieve(sieveSize):
"""
Returns a list of prime numbers calculated using
the Sieve of Eratosthenes algorithm.
"""
sieve = [True] * sieveSize
sieve[0] = False # zero and one are not prime numbers
sieve[1] = False
# create the sieve
for i in range(2, int(math.sqrt(sieveSize)) + 1):
pointer = i * 2
while pointer < sieveSize:
sieve[pointer] = False
pointer += i
# compile the list of primes
primes = []
for i in range(sieveSize):
if sieve[i] is True:
primes.append(i)
return primes
Nuestra funcion da x cantidad de números primos. Sieve en castellano es tamiz o colador.
Lo primero que hace nuestra función en Python es definir una lista con tantos elementos como numeros primos se desea. Esta lista llamada sieve se llena con valores de booleanos de tipo True. Esto es en principio todos los numeros son True, después se ira descartando cuales serán False.
En nuestro tamiz, sieve, descartamos al 0 y al 1 porque por definición no son números primos. Luego vamos desde el 2 hasta la raiz cuadrada de la cantidad de numeros primos que queremos (+ 1). Porque cómo dijimos antes queremos solo numeros pequeños porque luego descartaremos sus multiplos (en realidad hay una explicación un poco más compleja que la pueden leer del siguiente link: [1]. Luego descartamos todos los multiplos de estos números.
Por último, nos recorremos la lista buscando todos los que no quedaron descartados ( por no ser multiplos de otro número)
Una representación gráfica del algoritmo sería:
Bibliografía / Fuente de inspiración:
[1] https://inventwithpython.com/
[2] Wikipedia