java - 如何加快素数计算速度？

Question

我正在尝试回答以下欧拉问题(#10):

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

我的程序工作正常，但是我发现计算这个值需要 100 秒，使用以下代码，以 new Problem10().run() 作为起点:

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;
        }
    }
}

我该如何优化这个？如果可能的话，首先按照我当前的代码提出建议，然后提出完全不同的算法。

编辑，我也想避免有限的 Sieve of Eratosthenes ，作为这样一个迭代器的全部要点。流的目的是能够以无限数量的价格做到这一点，我自己不确定埃拉托色尼筛法是否适用于无限数量，我认为这不是微不足道的。

Answer 1

如果您观察到只需要考虑小于数字平方根的质因数，则可以减少 isPrime() 方法中的迭代次数。

所以当前的情况是:

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

可以改为:

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

可能还有其他可能性来优化您的代码，但这需要对您的代码进行详细审查。