代码之家 › 专栏 › 技术社区 › Blaine Mucklow

欧拉计划:问题7的程序优化?

primes java

Blaine Mucklow · 技术社区 · 16 年前

所以我解决了Euler项目的问题7:

第10001个素数是什么?

我成功地用Java解决了这个问题,但是当我运行我的解决方案时,它花费了8秒。我想知道如何从编程的角度而不是数学的角度来优化它。

数组循环和while语句是占用处理时间的主要因素吗?如何优化这一点?再说一遍,不要去寻找一个奇特的数学方程,在求解线程中有很多这样的方程。

扰流器

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

}

9 回复 | 直到 6 年前

mob 16 年前

long 而不是 BigInteger . A. 实例是一个成熟的Java对象,在创建和操作它们时有很多开销。

Bill the Lizard 16 年前

你可以自己做基准,但我猜 for (BigInteger bi : primesList) 循环是你花费大部分时间的地方。你正在遍历整个素数列表。当你到达一个素数候选除数,它大于你测试素数的平方根时,你就可以跳出这个循环。

~~另一个(相比之下非常微小的)改进是缓存 new BigInteger("2") BigInteger 每次通过while循环使用相同的值。~~

starblue 16 年前

也可以试试 Sieve of Erathostenes

Cine 16 年前

使用ints。为primesList使用一个固定大小的数组,这样就不必为内存分配付费(或者使起始大小足够大,以便动态列表不会出现问题)。

使用一个正常的计数整数,而不是计数外的循环。

JRL 16 年前

while(!prime) 在里面 getNextPrime() ,它保证返回一个素数,因此您可以在 fillList size()

另外,你可以试试 LinkedList 而不是 ArrayList . 在这个特定的用例中,它实际上可以更快。

Vishal 14 年前

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

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

Craig Stuntz 16 年前

我注意到你的代码测试了所有的候选者是否可以被2整除。但你的主要候选人永远都不是。所以你可以跳过第一次测试。这是件小事,但你可以省下9999个mod。

thorkia 16 年前

这是一个.NET解决方案。。。我的测试表明我在132ms中获得了10001prime,在4417ms中获得了100000 prime。

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

the_prole 12 年前

我只是翻译了 Sieve of Eratosthenes 变成了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

}