How to speed up my prime calculations?

Question

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.

Answer 1

The number of iterations in the method isPrime() can be reduced if you observe the fact that only the prime factors less than square root of a number need to be considerd.

So the current condition is :

  while (prime != null && prime.value <= number) 

It can be changed to :

   while (prime != null && prime.value <= square_root(number) )

There might be other possibilities to optimize your code but that would need detailed review of your code.

Answer 2

Here are some thoughts (not code since this appears to be a homework / project problem):

• Compute with ints not longs (int is good enough to hold 2 000 000) Though your sum of primes may need to be a long
• Only check odd numbers starting with 3 in your loop (why check an even number that you know is not prime>!
• Ensure you use minimum code possible .. there are lots of structures in your code. Wouldn't a simple loop over int values (and checking primes you have found only up to the sqrt of your value?)

And don't use square root function. Instead calculate the index of the largest prime you have to check as prime[p]*prime[p] so long as that is greater than your trial value. For example use something like this in your code (where ps is the index of the first prime you are checking, and iMax is primes[ps]*primes[ps] before you get into the loop. For efficiency of time, always use "strengh reductions" of calculations when you can.

while (i > iMax) { 
    ps++; iMax = primes[ps]*primes[ps];
};