[Aporte] Números primos

[razpeitia]

Vamos por pasos, primero:
¿Qué es un numero primo?
Vamos a definir un numero primo de una manera informal. Un primo es aquel número entero mayor o igual a 2. El cual es divisible entre 1 y el mismo.

Ejemplos de números primos:

Código:

 #  Divisores          Es primo?
 2  1, 2               Si
 3  1, 3               Si
 4  1, 2, 4            No
 5  1, 5               Si
 6  1, 2, 3, 6         No
 7  1, 7               Si
 8  1, 2, 4, 8         No
 9  1, 3, 9            No
10  1, 2, 5, 10        No
11  1, 11              Si
12  1, 2, 3, 4, 6, 12  No

Como podemos ver, 1 y el mismo numero siempre son divisores. Se puede demostrar matemáticamente, pero por cuestiones practicas no lo haremos.

Entonces lo único que tenemos que verificar es el rango de 2 a n - 1 si existe algún divisor, donde n es el numero que vamos a probar. Veamos una implementación sencilla.

Código:

def es_primo(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

Como podemos ver esta implementación es bastante deficiente ya que si queremos probar un numero grande entonces, este algoritmo tardara bastante.

Vamos a optimizarlo un poco.

Código:

def es_primo(n):
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

Como podemos ver la lógica es la misma, lo único que hicimos fue cambiar los limites. En vez de n - 1, utilizamos sqrt(n) como limite. Esto es por que si n tiene un divisor entonces este es menor o igual a sqrt(n). ¿Pueden imaginar por que?

Ahora que ya definimos que es numero primo y que tenemos funciones para saber si un numero es primo, generemos números primos.

Código:

primos = []
for i in range(2, n):
    if es_primo(i):
        primos.append(i)
print primos

Pero podemos generar primos de una manera mas eficiente usando la criba de Eratóstenes.
El procedimiento es simple:
1.- Empezamos con una lista de 2 hasta n. Todas posiciones inicialmente marcadas como Primo
2.- Recorremos la lista, si esta marcado como primo entonces marcamos todos sus múltiplos como NO primos. Si esta marcado como No primo ir al siguiente.
3.- Todas las posiciones que queden como primo, son primos.

Veamos una implementación:

Código:

l = set()
i = 2
while i*i <= n:
    if i not in l:
        j = i
        while i*j <= n:
            l.add(i*j)
            j += 1
    i += 1

for i in range(2, n+1):
    if i not in l:
        print i,

También existen métodos mas rápidos o que consumen menos memoria como:
La criba de atkin
O tests de primalidad mas rápidos como
Miller-Rabin