Project Euler: Numeros Primos

Numeros Primos, son aquellos números que se dividen entre si mismos y entre uno dando un residuo de 0.

Los primeros 6 numeros primos son: 2,3,5,7,11,13 , siendo el numero 2 el único numero primo par.




Con esa introduccion arrancamos al problema numero 7  de Project Euler el cual, en base al planteamiento anterior pide encontrar al numero primo numero 10001.

Una locura no?, sobretodo porque si analizamos el problema y si buscamos en internet sobre como saber si un numero es primo o no la realidad es que no existe una formula sino un algoritmo que nos dice que debemos dividir entre 2, entre 3, entre 5 y así en lo sucesivo hasta llega a la division del numero que estamos comprobando.

Si en alguna division aparte de 1 y el valor del mismo numero resulta tener un residuo de 0, ése numero no es primo.

Es facil con numeros de 1 al 10, e incluso del 1 al 100, pero obtener el numero primo numero 10,001 es un tanto más complicado.

Primer Intento: Division de 2 en Adelante

La primer solucion que se me ocurrio fué  comprobar en una funcion si es un numero primo o no, dividiendo entre 2 en adelante hasta llegar al valor que se comprueba.. Y funciona.

Pero el costo de tiempo fue enorme, tomó alrededor de 20 minutos en llegar al numero primo 10001.

Segundo Intento: Lista de Numeros Primos
La siguiente solucion fué crear una lista que almacene los numeros primos encontrados.

Para que?

Porque hay otra forma de encontrar un numero primo y es con el siguiente enunciado:

Un numero primo es aquel que no se divide entre otro numero primo

Entonces, cada que querramos ver si un numero es primo o no, habria que recorrer la lista para saber si es numero primo o no.
Si el resultado es falso, entonces habria que verificar mediante divisiones del 2 en adelante si es un numero primo, de serlo se agrega a la lista facilitando poco a poco la ubicacion de un numero primo.

El costo de tiempo para la solucion fue de 10 Minutos.

Tercer Intento: Reducir lista de rango de divisiones

No se me ocurrio otro titulo para el tercer intento.

Pero se basa basicamente en el primero, con la variante de que  vamos a reducir el rango de numeros a dividir para saber si es primo o no.

En  el primer intento, se usara un ciclo FOR que con valores del 2 al numero X (numero a comprobar si es primo o no), si enviamos de numero 198,340 el ciclo entonces se estaria repitiendo hasta 198,339 veces si es que no ocurre que otra division en el camino de un residuo de Cero.

Para el tercer intento reduciremos ése numero de posibilidades sacando la raiz cuadrada del numero enviado, redondearlo para que sea un entero y sumandole 1 porque virtualmente estamos comprobando a partir del numero 3 el cual tambien es primo, dado que los numero 1 y 2 son primos.

Teniendo esto en mente, y habiendo resuelto el problema de comprobar si un numero es primo o no, lo demás es sencillo.

Aqui mi solucion propuesta:


'''
Created on 01/01/2012
Project Euler - Problema 7

Enlistando los primeros seis numeros primos 2,3,5,7, 11 y 13,
podemos ver que el sexto numero primo es 13.

Cual es el 10,001vo Numero primo?
@author: Rafael Carrillo
@version: 1
'''

def isPrime(arg0):
    if arg0<2: #Si el numero enviado es menor a 2 es primo (no hay primos negativos)
        return True
    for x in range(2,int(arg0**.5)+1): #Reducir numero de posibilidades
        if arg0%x==0:
            return False #si en algun momento del a iteracion es TRUE, no es primo
    return True #Si no resulta ninguna division con residuo de 0, es primo

if __name__=='__main__':
    primes=0 #Numeros primos encontados
    n=2 #Empezar a buscar primos desde el numero 2
    lastPrime=0 #Ultimo numero primo encontrado
    while primes!=10001:  #Debemos encontrar 10001 numeros primos
        if isPrime(n):
            primes+=1
            lastPrime= n
        n+=1
    print lastPrime
            

El tiempo total que toma para obtener el resultado es de apenas 5.34 Segundos

Anuncios

Cuentanos tu reaccion

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s