0

Estoy realizando algunos ejercicios del sitio Project Euler y justo en el problema 9 "Summation of primes", pide calcular la suma de todos los números primos por debajo de 2,000,000, el inconveniente que tengo es que mi código funciona pero tarda mucho tiempo en darme la respuesta.

#include <iostream>
#include <conio.h>

using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
    
    string op;
    
    do{
        
        long int sum = 0;
        
        cout<<"Programa que calcula la suma de numeros primos por debajo de 2000000"<<endl;
        
        for(int i = 2; i < 2000000; i++){
            
            int cont = 0;
            
            for(int x = 1; x <= i; x++){
                
                if((i % x) == 0) cont++;
                
            }
            
            if(cont == 2) sum += i;
            
        }
        
        cout<<"\nLa suma de los numeros primos por debajo de 2000000 es: "<<sum<<endl;
        
        cout<<"\nDesea continuar: ";
        cin.ignore();
        getline(cin, op);
        
    }while(op == "si");
    
    getch();
    return 0;
}
2
  • 1
    Puedes comenzar el ciclo en 3 sumando de 2 en 2. Y así reduces las interacciones hasta la mitad. Esto porque un número divisible por un número par es divisible por 2. Solo deberías verificar antes del ciclo si es divisible por 2.
    – Mateo
    Commented el 13 feb. 2022 a las 2:22
  • Gracias Mateo, lo implemente y aunque es mas rápido, seguía algo lento. Commented el 13 feb. 2022 a las 23:54

1 respuesta 1

2

Una optimización inicial que podrías hacer a tu código es hasta qué punto analizas los divisores de un número

Existe una propiedad numérica en los divisores de un número tal que tiene parejas de divisores por lo que no es necesario evaluar todos los divisores hasta el número en sí sino solo hasta raiz cuadrada del número, con esa optimización inicial te quedaría:

        for(int i = 2; i < 2000000; i++){
            
            int cont = 0;
            
            for(int x = 1; x <= sqrt(i); x++) { // <---- Optimización
                
                if((i % x) == 0) cont++;
                
            }
            
            if(cont == 2) sum += i;
            
        }

Con esto reduces enormemente la cantidad de comparaciones a hacer.


Sin embargo existe un algoritmo aún más veloz para hacer el cálculo números primos llamado criba de eratóstenes el cual podrías revisar https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes

1
  • Muchas gracias Daniel, me sirvió, en especial lo ultimo que me comentaste sobre la criba de Eratóstenes la cual no sabia, un saludo! Commented el 13 feb. 2022 a las 23:51

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.