I'm trying to answer the following Euler Problem (#10):
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
My program is working correctly, however I found out that it took 100 seconds to compute this, using the following code, take new Problem10().run()
as starting point:
public class Problem10 extends Problem<Long> {
@Override
public void run() {
result = Iterators.finiteLongStream(new PrimeGenerator(), i -> i <= 2_000_000)
.sum();
}
@Override
public String getName() {
return "Problem 10";
}
}
public abstract class Iterators {
///
public static PrimitiveIterator.OfLong finiteLongIterator(final PrimitiveIterator.OfLong iterator, final LongPredicate predicate) {
return new PrimitiveIterator.OfLong() {
private long next;
@Override
public boolean hasNext() {
if (!iterator.hasNext()) {
return false;
}
next = iterator.nextLong();
return predicate.test(next);
}
@Override
public long nextLong() {
return next;
}
};
}
public static LongStream finiteLongStream(final PrimitiveIterator.OfLong iterator, final LongPredicate predicate) {
return Iterators.longStream(Iterators.finiteLongIterator(iterator, predicate));
}
public static LongStream longStream(final PrimitiveIterator.OfLong iterator) {
return StreamSupport.longStream(
Spliterators.spliteratorUnknownSize(iterator, 0), false
);
}
///
}
public class PrimeGenerator implements PrimitiveIterator.OfLong {
private final static LongNode HEAD_NODE = new LongNode(2);
private LongNode lastNode = HEAD_NODE;
private long current = 2;
@Override
public boolean hasNext() {
return true;
}
@Override
public long nextLong() {
if (lastNode.value == current) {
if (lastNode.next != null) {
long old = lastNode.value;
lastNode = lastNode.next;
current = lastNode.value;
return old;
}
return current++;
}
while (true) {
if (isPrime(current)) {
appendNode(current);
return current++;
}
current++;
}
}
private boolean isPrime(final long number) {
LongNode prime = HEAD_NODE;
while (prime != null && prime.value <= number) {
if (number % prime.value == 0) {
return false;
}
prime = prime.next;
}
return true;
}
private void appendNode(final long value) {
LongNode newNode = new LongNode(value);
couple(lastNode, newNode);
lastNode = newNode;
}
private void couple(final LongNode first, final LongNode second) {
first.next = second;
second.previous = first;
}
private static class LongNode {
public final long value;
public LongNode previous;
public LongNode next;
public LongNode(final long value) {
this.value = value;
}
}
}
How could I optimise this? If possible, first suggestions along the lines of my current code, then suggesting a totally different algorithm.
Edit, also I'd like to refrain from a finite Sieve of Eratosthenes, as the whole point of such an iterator resp. stream is to be able to do it for an infinite amount of prices, I am unsure myself whether the Sieve of Eratosthenes method works for infinite numbers, I think not trivially.