[Rectilíneo]

"Encuentra la suma de todos los primos menores a 2.000.000"

En Pyhton: primero he hecho una función que te diga si un número es primo o no. Después he hecho un bucle que recorra todos los números naturales menores a 2.000.000 y que los sume a un contador en caso de que sean primos.

El problema es que para sumar los primos menores a 100.000 tarda 36,7 segundos. Para los menores a 200.000 tarda 153,8 segundos. Tengo un problema porque el crecimiento de tiempo no es lineal

¿Alguien se anima a mostrarme un programa bien optimizado?

[mathtruco]

Hola Rectilíneo. Sospecho que el objetivo de la tarea será convencerse que decidir si un número es primo o no no es sencillo. ¿Puedes usar una lista de primos ya calculada, como https://primes.utm.edu/lists/small/10000.txt ?

[Ignacio Larrosa]

"Encuentra la suma de todos los primos menores a 2.000.000"

En Pyhton: primero he hecho una función que te diga si un número es primo o no. Después he hecho un bucle que recorra todos los números naturales menores a 2.000.000 y que los sume a un contador en caso de que sean primos.

El problema es que para sumar los primos menores a 100.000 tarda 36,7 segundos. Para los menores a 200.000 tarda 153,8 segundos. Tengo un problema porque el crecimiento de tiempo no es lineal

¿Alguien se anima a mostrarme un programa bien optimizado?

Pero el interes del proyecto Euler es hacerlo uno mismo ... Ahí te pongo el código de un programa que hice el año pasado en un curso de Python:

Código: [Seleccionar]

###############################################################
### PYTHON: Progrmación y Aplicación a la Enseñanza         ###
### ED16-05-PYTHON        Ignacio Larrosa Cañestro (c) 2016 ###
#########
###   Contar y sumar primos en un intervalo:
###      Primos.py
##############################

import math
import time

def primo(n):
    '''Determina si un entero es primo
    Argumentos: entero
    Imprime: nada
    Salida: Booleano
    '''
           
    ### Utiliza como candidatos a divisores los primos menores que 30
    ### y los p > 30, tales que mcd(p, 30) = 1

     
    l_pp = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]  ### 10 Primos < 30
    l_r30 = [1, 7, 11, 13, 17, 19, 23, 29]       ### 8 restos mod 30 primos con 30
    i, j, k = 0, 0, 0
    p = 2
    r = int(math.sqrt(n))
    esprimo = (n > 1)                            ### 1 no es primo
    while(esprimo and p <= r):
        if(n % p == 0):
            esprimo = False
        else:
            if(i < 9):
                i += 1
                p = l_pp[i]
            else:
                if(i == 9 or j == 7):
                    k += 1
                    i = 10
                    j = 0
                else:
                    j += 1
                p = 30*k + l_r30[j]
               
    return(esprimo)

def contPrimos(ini, fin):
    '''Cunta y suma los primos en el intervalo [ini, fin].
    Argumentos: enteros
    Imprime: número y suma de primos en el intervalo,
             porcentaje y tiempo de cálculo.
    Salida: Nada
    '''
    c, s = 0, 0
    t_ini = time.clock()
    for n in range (ini, fin + 1):
        if (primo(n)):
            c += 1
            s += n
    t = time.clock() - t_ini
    pc = 100*c/(fin + 1 - ini)
    print("En (",ini,", ",fin,") hay ",c," números primos que suman ",s,sep = "")
    print(pc,"% (",t," s)", sep="")

Y en sumar los primos menores que dos millones tarda en mi ordenador 47 s:

>>> contPrimos(1, 2000000)
En (1, 2000000) hay 148933 números primos que suman 142913828922
7.44665% (47.3733458653213 s)
>>>

Saludos,

[Ignacio Larrosa]

Ya puestos, veamos que ocurre hasta \( 10^7\textrm{ en paquetes de }2·10^6 \):

Código: [Seleccionar]

>>> contPrimos(1, 2000000)
En (1, 2000000) hay 148933 números primos que suman 142913828922
7.44665% (47.3733458653213 s)
>>> contPrimos(2000000,4000000)
En (2000000, 4000000) hay 134213 números primos que suman 401587815339
6.710646644676678% (72.85737635393969 s)
>>> contPrimos(4000000,6000000)
En (4000000, 6000000) hay 129703 números primos que suman 647889322993
6.485146757426621% (95.00472995364737 s)
>>> contPrimos(6000000,8000000)
En (6000000, 8000000) hay 126928 números primos que suman 888092534994
6.346396826801587% (108.59600792839149 s)
>>> contPrimos(8000000,10000000)
En (8000000, 10000000) hay 124802 números primos que suman 1122841492108
6.24009687995156% (120.48050594976985 s)
>>>
El método empleado es la llamada 'Wheel factorization' que ofrece una buena relación sencillez/eficiencia. Vamos, que es absolutamente elemental, pese a lo cual consigue una velocidad aceptable para este rango de números.

Saludos,

[Rectilíneo]

Pero el interes del proyecto Euler es hacerlo uno mismo ... Ahí te pongo el código de un programa que hice el año pasado en un curso de Python:

Código: [Seleccionar]

###############################################################
### PYTHON: Progrmación y Aplicación a la Enseñanza         ###
### ED16-05-PYTHON        Ignacio Larrosa Cañestro (c) 2016 ###
#########
###   Contar y sumar primos en un intervalo:
###      Primos.py
##############################

import math
import time

def primo(n):
    '''Determina si un entero es primo
    Argumentos: entero
    Imprime: nada
    Salida: Booleano
    '''
           
    ### Utiliza como candidatos a divisores los primos menores que 30
    ### y los p > 30, tales que mcd(p, 30) = 1

     
    l_pp = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]  ### 10 Primos < 30
    l_r30 = [1, 7, 11, 13, 17, 19, 23, 29]       ### 8 restos mod 30 primos con 30
    i, j, k = 0, 0, 0
    p = 2
    r = int(math.sqrt(n))
    esprimo = (n > 1)                            ### 1 no es primo
    while(esprimo and p <= r):
        if(n % p == 0):
            esprimo = False
        else:
            if(i < 9):
                i += 1
                p = l_pp[i]
            else:
                if(i == 9 or j == 7):
                    k += 1
                    i = 10
                    j = 0
                else:
                    j += 1
                p = 30*k + l_r30[j]
               
    return(esprimo)

def contPrimos(ini, fin):
    '''Cunta y suma los primos en el intervalo [ini, fin].
    Argumentos: enteros
    Imprime: número y suma de primos en el intervalo,
             porcentaje y tiempo de cálculo.
    Salida: Nada
    '''
    c, s = 0, 0
    t_ini = time.clock()
    for n in range (ini, fin + 1):
        if (primo(n)):
            c += 1
            s += n
    t = time.clock() - t_ini
    pc = 100*c/(fin + 1 - ini)
    print("En (",ini,", ",fin,") hay ",c," números primos que suman ",s,sep = "")
    print(pc,"% (",t," s)", sep="")

Y en sumar los primos menores que dos millones tarda en mi ordenador 47 s:

>>> contPrimos(1, 2000000)
En (1, 2000000) hay 148933 números primos que suman 142913828922
7.44665% (47.3733458653213 s)
>>>

Saludos,

No estaba teniendo en cuenta que para saber si \( n \) es primo tan solo hay que probar hasta \( \sqrt{n} \)... por eso tardaba tanto en calcularlo.

He hecho varios programas (probando con while, for, sin vectores, con vectores) y el que mejor me ha quedado utiliza un vector de números primos. Tarda 8.5 segundos en hacer la suma (en mi PC con un intel i5 4670 3.4GHz):

Código: [Seleccionar]

import time
import math
inicio=time.time()

a=3
b=2000000
primos=[2]
suma=2

while a<b:
    primo=True
    for i in primos:
        if i>math.sqrt(a):
            break
        if a%i==0:
            primo=False
            break
    if primo:
        primos.append(a)
        suma+=a
    a+=2 #los numeros pares no hace falta probarlos

final=time.time()
print "La suma es:",suma
print "Calculado en",final-inicio,"segundos."
Gracias por la ayuda ilarrosa

[feriva]

Hola, Rectilinieo.

Éste tarda más que el de Ilarrosa (tarda mucho menos, creí que eran 0,47 segundos, he leído mal) como un segundo o segundo y pico, depende de la versión de Python y el ordenador, pero es interesante; no se importa ningún módulo, ni siquiera el math, aprovecha un comando  que no tienen otros lenguajes, el “set”.

Python puede operar con conjuntos, así, si al guardar múltiplos de 2, de 3, etc., salen repetidos, el programa lo considera tal y como se considera en ZFC, sólo guarda los elementos, los datos no repetidos. Esto hace muy fácil programar la criba de Eratóstenes:

Código: [Seleccionar]


#-*- coding: utf-8 -*-

cont = 0

def criba (n):

global cont

numeros = set()  # Defino un conjunto en principio vacío llamado numeros


for j in range(2, n+1):  # Bucle que recorre desde 2 hasta n

if j not in numeros:  # Si j no está en el conjunto...

cont = (cont + j)  # Los va sumando y almacenando los j en cont

      numeros.update(range(j*j, n+1, j)) # Va cargando los j en el conjunto desde su cuadrado y saltando de j en j

criba (2000000)

print (cont)

Saludos.

[Ignacio Larrosa]

En mi ordenador tu programa tarda 42.15 s., 5 menos que el mio. Ir creando la lista de primos está bien si quieres hallar los primos de 1 a n, pero si quieres hallar los primos en [m, n] sin tener que volver a hallar los primeros es impracticable.

Por ejemplo:

Código: [Seleccionar]

>>> contPrimos(100000000,100001000)
En (100000000, 100001000) hay 54 números primos que suman 5400026920
5.394605394605395% (0.18662136316398814 s)
>>> contPrimos(1000000000,1000001000)
En (1000000000, 1000001000) hay 49 números primos que suman 49000023003
4.895104895104895% (0.5057995038597767 s)
>>> contPrimos(10000000000,10000001000)
En (10000000000, 10000001000) hay 44 números primos que suman 440000023286
4.395604395604396% (1.5249081531406716 s)
>>> contPrimos(100000000000,100000001000)
En (100000000000, 100000001000) hay 47 números primos que suman 4700000020699
4.695304695304696% (6.290014921286655 s)
>>> contPrimos(1000000000000,1000000001000)
En (1000000000000, 1000000001000) hay 37 números primos que suman 37000000018433
3.6963036963036964% (12.93284394691372 s)
>>>

Programando solo un poquito más, se pueden filtrar también los múltiplos de 3, considerando solo candidatos de la forma \( 6k\pm{}1 \), o los de \( 2, 3\textrm{ y }5 \), utilizando la lista de restos \( \textrm{mod }30 \) primos con \( 30 \). Pero no es mucho ahorro, pues los compuestos con estos factores se eliminan en seguida.

Todo esto en plan elemental, claro. Hay algoritmos mucho más sofisticados y rápidos.

Saludos,

[feriva]

En mi ordenador tu programa tarda 42.15 s., 5 menos que el mio.

Ah, pues entonces es prácticamente igual de eficiente, ya me extrañaba en ti, algo tenía que pasar.

El ordenador que tengo me lo dieron hace unos años; realmente es sólo una placa base con un microprocesador que está bien (todo sin caja ni nada) que tengo aquí conectada a los demás cachivaches encima de un soporte de pladur.

Pues con esto y en Linux (Ubuntu) y con Python 2 me tarda lo que decía; para no quedar por embaucador (que mi amigo Víctor Luis anda últimamente con la mosca detrás de la oreja en estas cuestiones) subo un vídeo de la ejecución:

Aquí:

https://foro.rinconmatematico.com/index.php?action=dlattach;topic=97445.0;attach=18769
 
Saludos.