3

所以我会称自己为一个相当新手的程序员，因为我在学校里主要专注于硬件，而不是很多计算机科学课程。

于是我解决了 Project Euler 的问题 7：

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

第10001个质数是多少？

我设法在 Java 中毫无问题地解决了这个问题，但是当我运行我的解决方案时，它需要 8 秒并更改几秒钟才能运行。我想知道如何从编程的角度而不是数学的角度来优化它。

数组循环和 while 语句是消耗处理时间的主要因素吗？以及如何优化？再次不要寻找一个花哨的数学方程..在解决方案线程中有很多。

SPOILER下面列出了我的解决方案。

public class PrimeNumberList {

private ArrayList<BigInteger> primesList = new ArrayList<BigInteger>();

public void fillList(int numberOfPrimes) {
    primesList.add(new BigInteger("2"));
    primesList.add(new BigInteger("3"));
    while (primesList.size() < numberOfPrimes){
        getNextPrime();
    }
}

private void getNextPrime() {
    BigInteger lastPrime = primesList.get(primesList.size()-1);
    BigInteger currentTestNumber = lastPrime;
    BigInteger modulusResult;
    boolean prime = false;
    while(!prime){
        prime = true;
        currentTestNumber = currentTestNumber.add(new BigInteger("2"));
        for (BigInteger bi : primesList){
            modulusResult = currentTestNumber.mod(bi);
            if (modulusResult.equals(BigInteger.ZERO)){
                prime = false;
                break;
            }
        }
        if(prime){
            primesList.add(currentTestNumber);
        }
    }
}

public BigInteger get(int primeTerm) {
    return primesList.get(primeTerm - 1);
}

}

4

9 回答 9

13

由于第 10001 个素数并没有那么大，您可以从使用long而不是BigInteger. 实例是一个BigInteger成熟的 Java 对象，在创建和操作它们时有很多开销。

于 2010-04-19T15:44:16.627 回答
6

您可以自己对其进行基准测试，但我猜想for (BigInteger bi : primesList)循环是您花费大部分时间的地方。您正在遍历整个素数列表。一旦你达到一个大于你正在测试素数的数字的平方根的素数候选除数，你就可以打破这个循环。

另一个（相比之下非常轻微）的改进是缓存和重用它，而不是每次通过 while 循环new BigInteger("2")创建一个具有相同值的新值。BigInteger<-- 仍然是一个很好的做法，但在这种情况下它不如舍入误差重要。

于 2010-04-19T15:46:22.473 回答
4

还可以尝试使用由 BitSet 表示的素数的 Erathostenes 筛，它比单独测试候选者要快得多。

于 2010-04-19T19:27:24.953 回答
1

使用整数。为您的 primesList 使用固定大小的数组，这样您就不必为内存分配付费（或使起始大小足够大，以使您的动态列表不会出现问题）。

使用一个法线来计算一个 int，而 Count 在循环之外。

于 2010-04-19T15:53:45.047 回答
1

由于您正在循环while(!prime)in getNextPrime()，因此可以保证返回一个素数，因此您可以更改循环 in而无需每次fillList调用​​。size()可能没有太大的收益，但是当你知道它每次增加 1 时计算大小有点没有意义。

此外，您可以尝试使用 aLinkedList而不是ArrayList. 在这个特定的用例中，它实际上可能更快。

于 2010-04-19T16:40:43.347 回答
1

你最好使用 int/long，然后通过循环来检查一个数字是否是素数。为了优化和加速您的程序，您可以通过将限制设置为 Math.sqrt(num) 来减少 for 循环中的迭代。

参考：http ://www.mycoding.net/2012/01/program-to-find-10001st-prime-number-project-euler-problem-7/

于 2012-01-17T06:16:09.923 回答
0

我注意到您的代码测试了所有候选者的可整除性。但是你的主要候选人从来都不是。所以你可以跳过第一个测试。这是一件小事，但你会节省 9999 个模组。

于 2010-04-19T16:19:51.900 回答
0

这是一个 .NET 解决方案...我的测试表明我在 132 毫秒内收到了第 10001 个质数，在 4417 毫秒内收到了 100,000 个质数。

public static IEnumerable<long> GetPrimes(int numberPrimes)
{
  List<long> primes = new List<long> { 1, 2, 3 };
  long startTest = 3;

  while (primes.Count() < numberPrimes)
  {
    startTest += 2;
    bool prime = true;
    for (int pos = 2; pos < primes.Count() && primes[pos] < Math.Sqrt(startTest); pos++)
    {
      if (startTest % primes[pos] == 0)
      {
        prime = false;
      }
    }
    if (prime)
      primes.Add(startTest);
  }
  return primes;
}
于 2010-04-19T19:51:18.990 回答
0

我只是简单地将埃拉托色尼筛法翻译成 Java。它应该是算法求解素数的最有效方法之一。

public static void main(String[] args){

    ArrayList<Integer> List = new ArrayList<Integer>();
    ArrayList<Integer> Primes = new ArrayList<Integer>();
    Primes.add(2);
    Integer p=2;
    Integer n=105000; 
    Integer i=1;

    while(p < n) {

        i=1;

        while((p*i)<=n) {
            List.add(p*i);
            i++;
        }

        while (p < n) {
            p++;
            if(List.contains(p)){                     }
            else                {Primes.add(p); break;}
        }

    }

    System.out.println("PRIME 10,001 is.... " + Primes.get(10000));
    // 104743

}
于 2014-03-10T20:49:57.910 回答