优化素数的计算 [英] Optimize calculation of prime numbers

问题描述

我正在尝试欧拉计画的问题3 ，我的算法实在太慢了。有人知道如何优化吗？我试图计算的数字是600851475143L。它需要永远计算，所以我需要一种加快计算速度的方法。

I am trying Problem 3 from Project Euler and my algorithm is far too slow. Does anyone know how to optimize this? The number I am trying to calculate up to is 600851475143L. It takes forever to calculate this so I need a way to speed up the calculations.

逻辑：

• 从3开始遍历所有数字，直到该数字为止- 1


• 对于这些数字中的每一个，请通过将它们除以它们之间的所有数字来检查它们是否为质数，如果不除以其中的任何一个，则它们为质数。



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

• Go through all the numbers from 3 until that number-1
• For each of these numbers check if they are prime by dividing them by all the numbers in between and if they dont divide by any of them then they are prime.

• If prime then add them to an array.

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

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

********** UPDATE **************

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

I calculated up to the square root which sped up the calculations a lot but I also done something else which was to add a break statement in the forloop to break once I discovered the number was not prime. I edited the code above to reflect these changes.

尽管我的算法在计算素因数上仍然是错误的，所以我需要对其进行研究并可能提出一个

My algorithm is still wrong for calculating the prime factors though so I will need to have a look at it and maybe raise a new question.

推荐答案

您不必除以每个数字。您只需将每个质数除以2和您的平方根即可。

You don't have to divide by every number. You only have to divide by each prime number between 2 and the square root of your number.

这篇关于优化素数的计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！