Java中的Euler #7项目

Question

Euler #7项目：

通过列出前六个素数: 2，3，5，7，11和13，我们可以看到第6素数是13。10001素数是什么？

这是我的解决方案：

public class PrimeFinder {

    public static void main(String[] args) {
        long time = System.nanoTime();
        int result = getNthPrime(10001);
        time = System.nanoTime() - time;
        System.out.println("Result: " + result
                + "\nTime used to calculate in nanoseconds: " + time);
    }
    
    private static int getNthPrime(int n) {
        int max = (int) (1.4 * n * Math.log(n));
        boolean[] isPrimeArray = new boolean[max + 1];
        for (int i = 2; i <= max; i++) {
            isPrimeArray[i] = true;
        }
        for (int i = 2; i * i <= max; i++) {
            if (isPrimeArray[i]) {
                for (int j = i; i * j <= max; j++) {
                    isPrimeArray[i * j] = false;
                }
            }
        }
        // Find the nth prime
        int nthPrime = 0;
        int index = 0;
        for(boolean isPrime : isPrimeArray) {
            if(isPrime) {
                nthPrime++;
            }
            if(nthPrime == n) {
                return index;
            }
            index++;
        }
        throw new IllegalArgumentException("n is not valid");
    }
}

它只需执行一个筛子，然后找到10001 true。

输出：

结果:以纳秒为单位计算的104743 时间: 13812289

问题：

1. 这显然是没有效率的。我该如何改进呢？
2. 有什么不好的做法吗？

Answer 1

与其在isPrime数组中循环一次，不如考虑在第一个for循环上扩展迭代，然后在达到预期结果后退出：

    ...
    int counter = 0;
    for (int i = 2; i <= max; i++) {
        if (isPrimeArray[i]) {
            if (++counter == n) {
                return i;
            }
            for (int j = i; i * j <= max; j++) {
                isPrimeArray[i * j] = false;
            }
        }
    }
    throw new IllegalArgumentException("n is not valid");

Answer 2

for (int i = 2; i \* i <= max; i++) {

在我的测试中，取max的平方根比在每次迭代中乘以i * i要快一些。

        for (int i = 2, limit = 1 + (int)Math.sqrt(max); i <= limit; i++) {

它只是一毫秒的一小部分，但有一个明显的差别。

for (int j = i; i \* j <= max; j++) { isPrimeArray[i \* j] = false; }

你可以简化一下。

                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }

然后，与其每次迭代执行两次乘法，还可以进行一次加法。当然，一个好的优化器会注意到，这两个乘法是相同的，只做一个。

我更喜欢不包括类型的名字，所以我把它叫做isPrime。

if(isPrime) { nthPrime++; } if(nthPrime == n) { return index; }

您比必要时更经常比较nthPrime和n。你可以直接说

            if (isPrime) {
                nthPrime++;

                if (nthPrime == n) {
                    return index;
                }
            }

其结果只能在nthPrime (或n )更改时才能更改(但n从不更改)。

顺便说一句，我尝试将for循环扩展为@h.j.k.建议，但它的运行速度比原始代码慢。只有一毫秒的一小部分，但速度更慢。

Answer 3

它可以大大缩短，这可能是有趣和更有效率的开发人员。

int prime = IntStream.range(2, Integer.MAX_VALUE)
        .filter(i -> IntStream.rangeClosed(2, (int) Math.sqrt(i))
                .noneMatch(n -> i % n == 0))
        .limit(10001).boxed()
        .collect(Collectors.reducing(null, (a, b) -> b));

这需要大约一秒钟的时间。