| Author: Eduardo Enriquez

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:

algoritmo de eratostenes


Bibliograf铆a / Fuente de inspiraci贸n:

[1] https://inventwithpython.com/

[2] Wikipedia

Related Posts