如何为Euler 7项目改进此代码？

Question

通过列出前六个质数：2、3、5、7、11和13，我们可以看到第6个质数是13。

第10 001个素数是多少？

我的解决方案：

public class Prime_Number {

    public static boolean isPrime(long n) {
        if ((n > 2 && n % 2 == 0) || (n > 3 && n % 3 == 0) || (n > 5 && n % 5 == 0) || n == 0 || n == 1) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int count = 0;
        int prime = 0;
        while (prime <= 10001) {
            if (isPrime(count) == true) {
                prime++;
                if (prime == 10001) {
                    System.out.println(count + " is a prime number" + "(" + prime + ")");
                }
            }
            count++;
        }
    }
}

但是它没有给出正确的答案。请帮助我升级代码。例如，程序将91定义为质数，但它不是质数。如何改善呢？

Answer 1

您需要针对每个小于质数平方根的质数测试数字，以确保它是质数。

您仅针对2,3和5进行测试。

因为存储所有素数并不总是在空间上可行的，所以一种常见的技术是测试2，然后测试从3开始的所有奇数。这需要循环。

考虑：

boolean isPrime(long n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    if (n < 9) return true;
    if (n % 3 == 0) return false;
    long max = (long)(Math.sqrt(n + 0.0)) + 1;
    for (int i = 5; i <= max; i += 6) {
        if (n % i == 0) return false;
        if (n % (i + 2) == 0) return false;
    }
    return true;
}