¿Porque mi algoritmo no funciona con cantidades más grandes?

Question

Problema:

El primo 41, se puede escribir como la suma de seis primos consecutivos:

41 = 2 + 3 + 5 + 7 + 11 + 13 Esta es la suma más larga de primos consecutivos que se suma a un primo por debajo de cien. ¿Qué primo, por debajo de un millón, se puede escribir como la suma de los primos más consecutivos?

El programa funciona con el número cien pero con un millón no es así, ¿qué podría hacer, o en donde esta el fallo?

Código

public static void main(String[] args) {

        System.out.println(primeSum(numbersPrimes(100)));

    }


    public static Vector primeSum(Vector vector){

       int suma = 0;
       Vector list = new Vector();

        for (int i = 0; i < vector.size(); i++) {

            suma = suma + (int) vector.get(i);

            if (isPrime(suma) & suma<100) {
                list.add(suma);
            } else {
            }

        }

        return (list);
    }



    public static Vector numbersPrimes(int num){

        Vector primes = new Vector(num);

        for (int i = 2; i < num; i++) {

            if(isPrime(i)){

                primes.add(i);
            }
        }
            return (primes);
        }


    public static boolean isPrime(int num){

        for (int i = 2; i < num; i++) {

            if(num % i == 0)

                return false;
        }

        return true;
    }

Answer 1

El problema es que tu método para calcular si un número es primo es muy lento. Siempre verificar todos los posibles divisores. Esto se puede optimizar de muchas maneras.

1. Memoization. Básicamente, consiste en guardar resultados de ejecuciones previas en memoria. Por ejemplo, si se sabe que el número X es primo, basta con calcularlo una sola vez, no 2 ni 3 ni muchas veces más. Aquí una forma de aplicar memoization en tu método:

   //colección para guardar los números primos
   static Set<Integer> primos = new HashSet<>();
   
   private boolean esPrimo(int n) {
       if (primos.contains(n)) return true;
       //implementación de validación de primo
   }
   

2. Optimización de algoritmo. Considera que todo número natural N siempre se puede dividir entre N y entre 1. Luego, el posible divisor de ese número hasta el que se debiese revisar es la raíz cuadrada del mismo, es decir, sqrt(N). Así que en lugar de intentar dividir N entre todos los números entre 2 y N-1, puedes reducir drásticamente esta ejecución al intentar dividir solo con los números entre 2 y sqrt(N). El código previo puede cambiar a:

   //colección para guardar los números primos
   static Set<Integer> primos = new HashSet<>();
   
   private boolean esPrimo(int n) {
       if (primos.contains(n)) return true;
       //implementación de validación de primo
       //primero calculemos la raíz cuadrada
       int raizCuadrada = (int)Math.sqrt(n);
       //ahora, se itera
       for (int i = 2; i <= raizCuadrada; i++) {
           if (n % i == 0) return false;
       }
       primos.add(n);
       return true;
   }
   

3. Usar solo números primos como posibles divisores del número. Todo número puede ser escrito como la multiplicación de múltiples números primos. Por ejemplo, el número 1564 puede ser escrito como 2 * 2 * 17 * 23. De la misma manera, se puede reducir la ejecución para no navegar por todos los números entre 2 y sqrt(N) aumentados de 1 en 1, sino por todos los números primos en ese rango. Podemos, entonces, cambiar el algoritmo a:

   //colección para guardar los números primos
   //se cambia a LinkedHashSet que permite mantener el orden
   //de inserción de los elementos
   static Set<Integer> primos = new LinkedHashSet<>();
   
   private boolean esPrimo(int n) {
       if (primos.contains(n)) return true;
       //implementación de validación de primo
       //primero calculemos la raíz cuadrada
       int raizCuadrada = (int)Math.sqrt(n);
       //ahora, se itera
       for (Integer i : primos) {
           if (i > raizCuadrada) break;
           if (n % i == 0) return false;
       }
       primos.add(n);
       return true;
   }
   

4. Para que la idea del punto 3 funcione, entonces los números primos deben calcularse en orden de aparición, y esto permitirá conocer, por ejemplo, varios números. Se puede pre calcular los números primos del 2 al 1 millón con esta idea.

   //colección para guardar los números primos
   //se cambia a LinkedHashSet que permite mantener el orden
   //de inserción de los elementos
   static Set<Integer> primos = new LinkedHashSet<>();
   
   private boolean esPrimo(int n) {
       if (primos.contains(n)) return true;
       //implementación de validación de primo
       //primero calculemos la raíz cuadrada
       int raizCuadrada = (int)Math.sqrt(n);
       //ahora, se itera
       for (Integer i : primos) {
           if (i > raizCuadrada) break;
           if (n % i == 0) return false;
       }
       primos.add(n);
       return true;
   }
   
   private void calcularPrimos(int maximo) {
       for (int i = 2; i <= maximo; i++) {
           esPrimo(i);
       }
   }
   

Ahora que ya tienes todos los números primos calculados, puedes usar el Set<Integer> primos para calcular la suma de los primos y si ese número es un primo. Aquí un ejemplo:

int tope = 100;
int maximoSumaPrimosConsecutivos = -1;
int suma = 0;
for (Integer i : primos) {
    if (i > tope) break;
    suma += i;
    if (primos.contains(suma) && suma < tope
        && suma > maximoSumaPrimosConsecutivos) {

        maximoSumaPrimosConsecutivos = suma;
    }
}
System.out.println(maximoSumaPrimosConsecutivos);

Answer 2

Te dejo este código que se probo con 100 y con 1000

import java.util.ArrayList;
import java.util.List;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author isaac
 */
public class SumaPrimos {

    public static List<Integer> primos = new ArrayList();

    public static void main(String[] args) {
        int maxNumero = 1000;
        int sumaMaxima = 0; //mayor suma de numeros primos consecutivos
        int longitudMaxima = 2;
        int longitudSumaPrimos = 2; //longitud de secuencia de números primos

        primos.add(2); //adicionamos el 2;

        //calculamos los números primos menores a maxNumero
        for (int i = 3; i <= maxNumero; i += 2) {
            if (isPrimo(i)) {
                primos.add(i);
            }
        }

       //Iniciamos a validar longitudes empezando por 2
        while(longitudSumaPrimos <= primos.size()){
            int sumaTemp = procesarSumas(longitudSumaPrimos, maxNumero);
            if(longitudSumaPrimos > longitudMaxima && sumaTemp > 0 ){
                sumaMaxima = sumaTemp;
                longitudMaxima = longitudSumaPrimos;
            }
            longitudSumaPrimos++;
        }

        System.out.println(longitudMaxima);
        System.out.println(sumaMaxima);
    }

    public static boolean isPrimo(int numero) {
        boolean primo = true;

        int raiz = (int) (Math.sqrt(numero));

        for (Integer i : primos) {
            if (i > raiz) {
                break;
            }
            if (numero % i == 0) {
                primo = false;
                break;
            }
        }

        return primo;
    }

    public static int procesarSumas(int longitud, int maxSuma) {
        System.out.println("***** Procesando longitud " + longitud + " *****");
        int sumaMaximaPrima = 0;
        int indexInicial = 0;
        int indexFinal = indexInicial + longitud - 1;

        /*
        Si la longitud es impar no sumo el indice 0 que contiene al 2
        */
        if(longitud % 2 != 0){
            indexInicial++;
            indexFinal++;
        }

        while (indexFinal < primos.size()) {
            int sumaParcial = 0;
            for (int i = indexInicial, j = indexFinal; i <= j; i++) {
                sumaParcial += primos.get(i);
            }
            /*
            Si la suma parcial es mayor al número maximo no seguimos la busqueda
            */
            if(sumaParcial > maxSuma){
                break;
            }

            if(existeEnPrimos(sumaParcial)){
                sumaMaximaPrima = sumaParcial;
            }
            /*
            si la longitud es par solo hacemos una suma, descartamos el resto 
            de sumas por que van a dar par. 
            */
            if (longitud % 2 == 0) {
                break;
            }
            indexInicial++;
            indexFinal++;
        }

        System.out.println("Suma Maxima Prima para longitud " + longitud + " es " + sumaMaximaPrima);
        return sumaMaximaPrima;
    }

    public static int sumarPrimos(int indexInicio, int indexFinal) {
        int suma = 0;

        for (; indexInicio <= indexFinal; indexInicio++) {
            suma += primos.get(indexInicio);
        }

        return suma;
    }

    public static boolean existeEnPrimos(int numero) {
        return primos.contains(numero);
    }

}