Obtener numeros primos con Python

06/18/2017 | Author: Eduardo Enriquez

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:

algoritmo de eratostenes


Bibliografía / Fuente de inspiración:

[1] https://inventwithpython.com/

[2] Wikipedia


Tags