Foros del Web » Programando para Internet » Python »

[Aporte] Números primos

Estas en el tema de [Aporte] Números primos en el foro de Python en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 12/12/2010, 01:21
Avatar de razpeitia
Moderador
 
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 19 años, 3 meses
Puntos: 1360
[Aporte] Números primos

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

Última edición por razpeitia; 14/12/2010 a las 12:17

Etiquetas: primos, aportes
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 3 personas




La zona horaria es GMT -6. Ahora son las 10:18.