How much time should it take to find the sum of all prime numbers less than 2 million?
- by Shahensha
I was trying to solve this Project Euler Question. I implemented the sieve of euler as a helper class in java. It works pretty well for the small numbers. But when I input 2 million as the limit it doesn't return the answer. I use Netbeans IDE. I waited for a lot many hours once, but it still didn't print the answer. When I stopped running the code, it gave the following result
Java Result: 2147483647
BUILD
SUCCESSFUL (total time: 2,097 minutes
43 seconds)
This answer is incorrect. Even after waiting for so much time, this isn't correct. While the same code returns correct answers for smaller limits.
Sieve of euler has a very simple algo given at the botton of this page.
My implementation is this:
package support;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author admin
*/
public class SieveOfEuler {
int upperLimit;
List<Integer> primeNumbers;
public SieveOfEuler(int upperLimit){
this.upperLimit = upperLimit;
primeNumbers = new ArrayList<Integer>();
for(int i = 2 ; i <= upperLimit ; i++)
primeNumbers.add(i);
generatePrimes();
}
private void generatePrimes(){
int currentPrimeIndex = 0;
int currentPrime = 2;
while(currentPrime <= Math.sqrt(upperLimit)){
ArrayList<Integer> toBeRemoved = new ArrayList<Integer>();
for(int i = currentPrimeIndex ; i < primeNumbers.size() ; i++){
int multiplier = primeNumbers.get(i);
toBeRemoved.add(currentPrime * multiplier);
}
for(Integer i : toBeRemoved){
primeNumbers.remove(i);
}
currentPrimeIndex++;
currentPrime = primeNumbers.get(currentPrimeIndex);
}
}
public List getPrimes(){
return primeNumbers;
}
public void displayPrimes(){
for(double i : primeNumbers)
System.out.println(i);
}
}
I am perplexed! My questions is
1) Why is it taking so much time? Is there something wrong in what I am doing?
Please suggest ways for improving my coding style, if you find something wrong.
