如何为Project 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;
}