Euler #7项目优化

Question

我注意到了一些Euler项目问题的主题。它们需要大量的时间来完成。(像最大的回文和1001Prime这样的问题)我希望能有一些方法来优化代码，使其更好。我让它跑了超过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;
      }

如果您想优化更多，可以将素数存储在数组中，并且只检查可被前一个素数整除的数字。

Answer 2

这个程序打印10001个第一个素数。正如@Tejash Desai所建议的，可以进行两个优化：

(一)将已发现的素数保存在一个列表中，以便只对该列表中的项目进行新素数的测试，而不是对所有奇数进行测试；

(2)只对一个数的平方根进行因子检验。

void printPrimes() {
    // Find first 10001 primes
    int p = 0;
    for (var i = 2; i <= 10001; i++) {
        p = nextPrime();
        Console.WriteLine("Prime #{0}: {1}", i, p);
    }
}

// Set of known primes
List<int> primes = new List<int>() {2};

// Find the prime next to the last one that was found
int nextPrime() {
    int k = primes[primes.Count - 1] + 1;
    while (!testPrimeUsingKnownSetOfPrimes(k)) {
        k = k + 1;
    }

    primes.Add(k);
    return k;
}

// Check if a number is prime, using the set of known primes
bool testPrimeUsingKnownSetOfPrimes(int n) {

    foreach (var p in primes) {
        // Largest prime factor of a number can't be greater than square root of the number
        if (p > Math.Sqrt(n)) {
            return true;
        }

        if (n % p == 0) {
            return false;
        }
    }

    return true;
}

PS用C#编写。

Answer 3

循环，直到小于或等于n的平方根。

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

另外，另一个优化是将到目前为止遇到的所有素数都存储在ArrayList中，然后只遍历列表中的循环。

//Check for non-prime odd numbers for(int i = 0; i <= arrayList.size(); i ++) { if(num % arrayList.get(i) == 0) return false; }             arrayList.add(num);