Problem:
The 41st prime can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13 This is the largest sum of consecutive primes that adds to a prime under one hundred. Which prime, under a million, can be written as the sum of the most consecutive primes?
The program works with the number one hundred but with a million it doesn't, what could I do, or where is the error?
Code
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;
}
The problem is that your method to calculate if a number is prime is very slow. Always check all possible dividers. This can be optimized in many ways.
Memoization . Basically, it consists of saving results of previous executions in memory. For example, if it is known that the number X is prime, it is enough to calculate it only once, not 2 or 3 or many more times. Here is a way to apply memoization in your method:
Algorithm optimization. Consider that every natural number N can always be divided by N and by 1. Then, the possible divisor of that number up to which it should be revised is its square root, that is, sqrt(N). So instead of trying to divide N by all the numbers between 2 and N-1, you can drastically reduce this performance by trying to divide only by the numbers between 2 and sqrt(N). The above code may change to:
Use only prime numbers as possible divisors of the number. Every number can be written as the multiplication of multiple prime numbers. For example, the number 1564 can be written as 2 * 2 * 17 * 23. In the same way, the execution can be reduced so as not to navigate through all the numbers between 2 and sqrt(N) increased by 1, but by all prime numbers in that range. We can then change the algorithm to:
For the idea of point 3 to work, then the prime numbers must be calculated in order of appearance, and this will allow knowing, for example, several numbers. You can precalculate the prime numbers from 2 to 1 million with this idea.
Now that you have all the primes calculated, you can use the
Set<Integer> primos
to calculate the sum of the primes and whether that number is a prime. Here an example:I leave you this code that was tested with 100 and with 1000