3

n番目の素数を見つけるために、以下のコードを書きました。これは時間の複雑さで改善できますか?

説明：

ArrayList arr には、計算された素数が格納されます。arr がサイズ「n」に達すると、ループが終了し、ArrayList の n 番目の要素を取得します。素数を計算する前に数字 2 と 3 が追加され、4 から始まる各数字が素数であるかどうかがチェックされます。

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>(); // stores prime numbers 
                                                      // calculated so far
    // add prime numbers 2 and 3 to prime array 'arr'
    arr.add(2); 
    arr.add(3);

    // check if number is prime starting from 4
    int counter = 4;
     // check if arr's size has reached inp which is 'n', if so terminate while loop
    while(arr.size() <= inp) {
        // dont check for prime if number is divisible by 2
        if(counter % 2 != 0) {
            // check if current number 'counter' is perfectly divisible from 
           // counter/2 to 3
            int temp = counter/2;
            while(temp >=3) {
                if(counter % temp == 0)
                    break;
                temp --;
            }
            if(temp <= 3) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp));
    }
}
4

4 に答える 4

10

はい。

あなたのアルゴリズムはO（n ^ 2）操作を行います（正確ではないかもしれませんが、そう思われます）。nは結果です。

O(ipn* log(log(n)))を取るhttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenesアルゴリズムがあります。その中にinpステップのみを作成でき、 n = 2ipn*ln(ipn)と仮定します。 nはipn -primeより大きくなければなりません。(素数の分布はわかっていますhttp://en.wikipedia.org/wiki/Prime_number_theorem )

とにかく、既存のソリューションを改善できます。

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    arr.add(2);
    arr.add(3);

    int counter = 4;

    while(arr.size() < inp) {
        if(counter % 2 != 0 && counter%3 != 0) {
            int temp = 4;
            while(temp*temp <= counter) {
                if(counter % temp == 0)
                    break;
                temp ++;
            }
            if(temp*temp > counter) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp-1));
    }
}
于 2013-02-07T02:48:25.140 に答える
2

それをスピードアップするためにできるいくつかのこと：

  1. カウンターを 5 から開始し、1 ではなく 2 ずつ増やしてから、ループで mod 2 をチェックしないでください。
  2. temp を counter / 2 で開始する代わりに、最初の奇数 <= int(sqrt(counter)) で開始します。
  3. 温度を 2 下げる。

複雑さの改善につながるかどうかはわかりませんが、上記の (2) は O(n^2) から O(n*sqrt(n)) になります。

于 2013-02-07T02:47:03.753 に答える