3

私は大学でITを勉強している学生です。私は1兆を超える素数を検索する割り当てを与えてきました。手順が示されています：

  • 1兆としての開始数

  • 奇数の候補を選択する

  • 3と平方根の間のすべての奇数の整数でそれらを除算します。整数の1つが候補を均等に分割する場合、それは素数として宣言されます。

今これは私が思いついたものです：

import java.io.*;
import javax.servlet.*;
import javax.servlet.http.*;

public class PrimeSearcher extends HttpServlet{
    private long number = 10000000000000001L;
private boolean found = false;
public void doGet(HttpServletRequest request, HttpServletResponse response) throws IOException, ServletException {
    PrintWriter out = response.getWriter();

    while(!checkForPrime(number)){
        number = number+2;
    }

    if(found){
        out.println("The first prime number above 1 quadrillion is : " + number);
    }

}

public boolean checkForPrime(long numberToCheck){
    double sqrRoof = Math.sqrt(numberToCheck);
    for(int i=3; i< sqrRoof; i++){
        if(numberToCheck%i==0){
         return false;
        }
    }
    found= true;
    return found;
}


}

私の心配は、正しい道を進んでいるかどうかわからないことです。別の問題は、これが常に1つの番号、最初の番号であるということです。グーグルした後、servlet.comとjavafaqで、スレッドを使用していることがわかりました。スレッドを実行しましたが、かっこいいようです。私はそれを本当に理解していませんが、それは異なる数を与えます。

だから私は今、そのアルゴリズムを実装する方法について混乱していて、本当にそれをコピーしたくありません。たぶん彼らの方法を理解した後、私はこのアルゴリズムをより良くコーディングすることができます。

ありがとう

4

4 に答える 4

1

見た目は大丈夫だと思いますが、タイプiである必要があるかもしれません。また、2ずつインクリメントすることはありません（奇数の除数をチェックするだけで済みます）。checkForPrimelongi

これには長い時間がかかることに備えてください.......

于 2012-08-23T08:10:37.983 に答える
1

checkForPrimeさらに、までする必要がありますi<=sqrRoof（sqrRoofは整数である可能性があります）。

于 2012-08-23T08:44:12.540 に答える
1

ソースコードには1兆ではなく、10兆が書かれています。ちょうどあなたが知っているので。:)

それらが必要な場合、1兆を超える素数は次のとおりです。

37,91,159,187,223 ...

10兆を超える：

61,69,79 ...
于 2012-08-23T10:16:46.323 に答える
1

大きな素数をチェックする標準的な方法は、エラトステネスのふるいを使用して、ある限界までの低い素数のリストを生成することです。そのリストを使用して、クアッドリリオンの範囲の奇数をチェックし、ほとんどの非素数を排除します。

次に、ミラーラビン確率素数検定を使用して、残っている多数が本当に素数であるかどうかを確認します。MRテストを最大64回繰り返すと、誤って合成数を見つけた場合よりも、ハードウェアが故障した可能性がはるかに高くなります。

MRテストは、多数の試行除算よりもはるかに高速です。

于 2012-08-23T13:57:52.077 に答える