Proyecto Euler problema 10:sumatoria de primos

Tras leer los términos del proyecto Euler, hemos decidido dejar de publicar resultados. Si bien en un principio nos pareció interesante comentar las soluciones con nuestros lectores, respetamos la decisión de esa página. No vamos a borrar los posts antiguos, porque tampoco 10 problemas sencillos creemos que causen ningún estropicio, pero en el futuro no publicaremos más avances. Si alguien nos escribe con alguna duda concreta de un problema, estaremos encantados de dedicarle un post a analizar la estrategia de resolución, pero no publicaremos más código.

De vuelta con los números primos, encontramos un problema que, si bien aparentemente sencillo, nos obliga a estudiar un poquito sobre los primos y sus características, pues el método de «fuerza bruta» no funcionará, al menos no con los ordenadores actuales en menos de un minuto.

La suma de los primos por debajo de 10 es 2+3+5+7 = 17.

Encuentra la suma de todos los números primos por debajo de dos millones

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

La solución a este problema aplica la criba de Erastótenes, en la cual hacemos una lista de números tan grande como vamos a necesitar (en este caso, dos millones). Lo que haremos será ir tomando uno por uno los números y, si son primos, ir tachando todos sus múltiplos. No tendremos que hacer divisiones, sino simplemente ir recorriendo en orden los números que no hemos tachado, empezando en el 3 y siendo todos impares, pues serán los que no son múltiplos de un número anterior. Con ellos vamos construyendo una lista que tendrá todos los primos por debajo del número indicado.

En el cálculo de la suma podríamos haber usado la siguiente función: suma=reduce(lambda x, y: x+y, miListaPrimos), pero dejamos un algoritmo más «tradicional» para los lectores que no están familiarizados con la función reduce de python.

¿Alguna duda sobre nuestra solución? ¡Escríbela en los comentarios!

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

Deja un comentario

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

Publicaciones relacionadas

Comienza escribiendo tu búsqueda y pulsa enter para buscar. Presiona ESC para cancelar.

Volver arriba