优化素数的计算[重复]

Question

我正在尝试欧拉项目的问题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语句，一旦我发现数字不是素数，就中断。我编辑了上面的代码以反映这些更改。

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

Answer 1

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

如果你需要额外的性能，那么使用埃拉托色尼筛子。这允许你使用以前素数的结果来减少确定较大数字是否是素数的工作。

Answer 2

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