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ステートメントを追加してbreakするという別のことも行いました。これらの変更を反映するために、上記のコードを編集しました。

私のアルゴリズムはまだ素数を計算するのに間違っているので、それを見て、新しい質問をする必要があります。

4

2 に答える 2

6

すべての数値で割る必要はありません。2とあなたの数の平方根の間の各素数で割る必要があるだけです。

于 2013-03-27T00:22:11.320 に答える
4

最初にできることは、テストしている数値の平方根までの可能な因子のみをテストすることです。平方根よりも大きい因子が見つかった場合は、平方根よりも小さい因子が見つかったはずだからです。

追加のパフォーマンスが必要な場合は、エラトステネスのふるいを使用してください。これにより、以前の素数の結果を使用して、より大きな数が素数であるかどうかを判断する作業を減らすことができます。

于 2013-03-27T00:22:03.660 に答える