Another simple straight forward question from Project Euler. The idea was to re-use the prime number generator that I had written for the problem number 7. It was a simple thing of letting my array grow till the last prime found was greater than 2 million, and then sum up all the elements in the array. Not much to write about. Here’s the code that ran in 3468ms on my machine:
public class Problem_10 {
public long getSumOfPrimes(int maxPrime) {
List<Long> primes = new ArrayList<Long>();
primes.add(2L);
long sum = 2L;
long lastPrime = 2L;
long num = 3L;
// Start the stopwatch
Stopwatch stopwatch = new Stopwatch();
stopwatch.start();
// Search for primes by dividing num with all the known prime numbers
while (lastPrime < maxPrime) {
boolean isComposite = false;
double sqrt = Math.sqrt(num);
for (long p : primes) {
if (p > sqrt)
break;
if (num % p == 0) {
isComposite = true;
break;
}
}
if (!isComposite) {
primes.add(num);
lastPrime = num;
if (num < maxPrime)
sum += num;
}
num++;
}
stopwatch.stop();
System.out.println("The reading for operation is: " + stopwatch);
return sum;
}
public static void main(String[] args) {
System.out.println((new Problem_10()).getSumOfPrimes(2000000));
}
}
Here since the upper bound was already known to me, using the Sieve of Eratosthenes would be the better way to go about things. Further optimization ignores all the even numbers as 2 is the only even prime. In this case, the ith element represents the number 2i + 1
Popularity: 14% [?]
Related posts:
