如何为Project Euler 7改进此代码？ [英] How can I improve this code for Project Euler 7?

问题描述

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

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

什么是第10个001素数？

What is the 10 001st prime number?

我的解决方案：

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定义为素数，但它不是素数。如何改进它？

But it does not give a correct answer. Please help me to upgrade my code. For instance, program defines a 91 as a prime number, but it is not a prime number. How to improve it?

推荐答案

你需要测试每个素数小于其平方根的数字，以确保它是素数。

You need to test the number against every prime less than its square root to ensure it is prime.

你只是针对2,3和5进行测试。

You're only testing against 2,3 and 5.

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

Because storing all the primes is not always space-feasable, a common technique is to test for 2, and then test all odd numbers starting at 3. This requires a loop.

考虑：

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

这篇关于如何为Project Euler 7改进此代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！