Proyecto Euler problema 7: primo número 10001 (diezmilesimoprimer primo)

Este es un problema que se repite a lo largo del proyecto Euler: calcular primos, en concreto calcular un primo concreto, en una de sus variantes. Veamos el enunciado.

Si hacemos una lista de los seis primeros números primos: 2,3,5,7,11 y 13, podemos ver que el 6º primo es el 13.

¿Cuál es el 10001er número primo?

Por favor, intenta participar del espíritu del proyecto, y utiliza nuestras soluciones sólo para compararlas con las tuyas.

La solución que presentamos en este caso también se trata de un algoritmo de «fuerza bruta». Básicamente vamos barriendo todos los números enteros y haciendo una lista con todos los números primos. Para saber si un entero es primo, lo dividimos por todos los valores que tenemos en nuestra lista de primos y por todos los siguientes enteros desde el mayor primo conocido hasta el momento hasta la raíz cuadrada del número.  Es muy fácil de entender, una solución que parte de la definición de números primos y alguna propiedad, pero para primos mayores tendremos que echar mano de algoritmos más complicados como la criba de Erastótenes (en un artículo próximo necesitaremos utilizarla, pues la fuerza bruta no será suficiente para resolver el problema en menos de un minuto).

numeroAEvaluar=1
divisorActual=2
maxPrimo=2
listaPrimos=[2] #iniciamos con el primer primo conocido
cuenta=0
while len(listaPrimos)<10001:
 numeroAEvaluar+=2 #los primos seran siempre impares
 esPrimo=True
 for i in listaPrimos:
 if numeroAEvaluar%i==0:
 esPrimo=False
 break
 if not esPrimo:
 continue 
 divisorActual=maxPrimo
 while divisorActual<=numeroAEvaluar**0.5:#ver propiedades de los primos
 if numeroAEvaluar%divisorActual==0:
 break
 divisorActual+=1
 if divisorActual>numeroAEvaluar**0.5:
 maxPrimo=numeroAEvaluar
 listaPrimos.append(numeroAEvaluar)
 print maxPrimo,len(listaPrimos)
 
print "10001th prime is",maxPrimo

¿Tienes una solución interesante al problema? ¿Alguna duda sobre nuestra solución? ¡Escríbela en los comentarios!

(Visto 1.439 vecess, 1 visitas hoy)
¡Comparte este articulo!

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *