java - 欧拉计划 #7 优化

Question

我一直在关注一个与欧拉计划问题相关的主题。它们需要大量时间才能完成。 (像 Largest Palindrome 和 10,001st Prime 这样的问题)我希望有一些方法可以优化代码以使其更好。我让它运行了超过 24 分钟，但它没有完成。

public class Seven
{
    public static void main(String[] args)
    {
        //Declare Variables
        int primeCount = 0;
        int numCount = 1;
        int latestPrime = 0;

        while(primeCount <= 10001)
        {
            if(isPrime(numCount))
            {
                primeCount++;
                latestPrime = numCount;
            }
            numCount++;
        }

        System.out.println("The 10,001st prime is: " + latestPrime);
    }

    //This method will determine if a number is prime
    public static boolean isPrime(long num)
    {
        //Check for even number
        if(num % 2 == 0)
            return false;

        //Check for non-prime odd numbers
        for(long i = 3; i <= num; i += 2)
        {
            if(num % i == 0)
                return false;
        }

    //Return that the number is prime
        return true;
}

Answer 1

你做了很多重复，你不需要在 for 循环中遍历整个数字，直到平方根为止。

这会在一秒钟内运行。

 // Check for non-prime odd numbers
      for (long i = 3; i <= Math.sqrt(num) +1; i += 2) {
         if (num % i == 0)
            return false;
      }

如果你想进一步优化，你可以将质数存储在一个数组中，并且只检查这个数是否可​​以被前面的质数整除。