3

我正在尝试Project Euler 的问题 3 ，但我的算法太慢了。有谁知道如何优化这个？我要计算的数字是 600851475143L。计算这个需要很长时间，所以我需要一种方法来加快计算速度。

逻辑：

  • 遍历从 3 到该数字 1 的所有数字
  • 对于这些数字中的每一个，通过将它们除以它们之间的所有数字来检查它们是否为素数，如果它们不除以它们中的任何一个，则它们是素数。

  • 如果素数，则将它们添加到数组中。

    public static void problem3(long number){

long number2 = number;
long sqrtNumber = (long)Math.sqrt(number2);


int indexNum = 1;
boolean isPrime = false;

int primeNums[] = new int[2];
primeNums[0] = 2;

//puts prime numbers into an array
for(int y = 3; y < sqrtNumber; y++){
   isPrime=true;
   for(int theNum = 2; theNum < y; theNum++){
       //if y divides evenly by any number then it is not prime         
       if(y%theNum==0){
           //dont store in array
           isPrime=false;
           break;
       }
   }

   if(isPrime == true){
       //add to array
       System.out.println(y);
       //put y in the array and exapnd the array
       //System.out.println("y: " + y);
       primeNums[indexNum] = y;

       int[] newArray = new int[primeNums.length + 1];
       System.arraycopy(primeNums, 0, newArray, 0, primeNums.length);

       primeNums = newArray;

       indexNum++;
   }
}

********** 更新 **************

我计算到了平方根，这大大加快了计算速度，但我还做了其他事情，即在我发现数字不是素数时在 forloop 中添加一个 break 语句来中断。我编辑了上面的代码以反映这些变化。

我的算法在计算主要因素时仍然是错误的，所以我需要看看它，也许会提出一个新问题。

4

2 回答 2

6

您不必除以每个数字。你只需要除以 2 和你的数字的平方根之间的每个素数。

于 2013-03-27T00:22:11.320 回答
4

您可以做的第一件事是仅通过您正在测试的数字的平方根来测试可能的因子，因为如果您找到一个大于平方根的因子，那么您应该找到一个小于平方根的因子。

如果您需要额外的性能，请使用埃拉托色尼筛。这使您可以使用先前素数的结果来减少确定较大数字是否为素数的工作。

于 2013-03-27T00:22:03.660 回答