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