10

次の方法を検討してください。

public static boolean isPrime(int n) {
    return ! (new String(new char[n])).matches(".?|(..+?)\\1+");
}

私は正規表現の第一人者ではありませんでしたが、この方法が実際にどのように機能するかを誰かが完全に説明できますか？さらに、整数が素数であるかどうかを判断するための他の可能な方法と比較して効率的ですか？

4

3 に答える 3

10

まず、この正規表現は、一進法で表される数に適用されることに注意してください。

1       is 1
11      is 2
111     is 3
1111    is 4
11111   is 5
111111  is 6
1111111 is 7

等々。実際には、どの文字でも使用できます（したがって、.式のs）が、「1」を使用します。

次に、この正規表現は合成（非素数）数と一致することに注意してください。したがって、否定は素数性を検出します。

説明：

式の前半、

.?

文字列""（0）と "1"（1）は一致している、つまり素数ではないことを示します（定義上、議論の余地はありますが）。

後半は、簡単な英語で次のように述べています。

長さが2以上の最短の文字列、たとえば「11」（2）に一致します。次に、文字列全体を繰り返して一致させることができるかどうかを確認します。「1111」（4）は一致しますか？「111111」（6）は一致しますか？「11111111」（8）は一致しますか？等々。そうでない場合は、次に短い文字列「111」（3）で再試行します。等。

これで、元の文字列をその部分文字列の倍数として一致させることができない場合、定義上、それが素数であることがわかります。

ところで、欲張りでない演算子?は、「アルゴリズム」を最短から開始してカウントアップするものです。

効率：

興味深いですが、確かに効率的ではありません。さまざまな議論があります。その一部を以下にまとめます。

  • @TeddHoppが指摘しているように、よく知られているエラトステネスのふるいのアプローチでは、2と3の倍数をチェックしているときに、すでに「訪問」されている4、6、9などの整数の倍数をチェックする必要はありません。アプローチは、すべての小さい整数を徹底的にチェックします。

  • @PetarMinchevが指摘しているように、数値の平方根に達すると、倍数チェックスキームを「短絡」することができます。平方根より大きい因数は平方根より小さい因数とパートナーを組む必要があるため（そうでない場合、平方根より大きい2つの因数は数より大きい積を生成するため）、この大きい因数が存在する場合は、そうすれば、私たちはすでにより小さな要因に遭遇した（したがって一致した）はずです。

  • @Jesperと@Brianが簡潔に述べているように、非アルゴリズムの観点から、たとえば9000の場合、文字列を格納するためにメモリを割り当てることから正規表現がどのように始まるかを考えてみてください。;） char[9000]

  • @Foonが指摘しているように、常に正しいとは限りませんが（代わりに擬素数を上げる）、より大きな数に対してより効率的である可能性のある確率的手法が存在します。しかし、100％正確で、ふるいベースの方法よりもはるかに効率的な決定論的テストもあります。Wolfram'sには素晴らしい要約があります。

于 2012-10-03T19:57:08.227 に答える
5

素数の単項特性と、これが機能する理由については、すでに説明しました。したがって、従来のアプローチとこのアプローチを使用したテストを次に示します。

public class Main {

    public static void main(String[] args) {
        long time = System.nanoTime();
        for (int i = 2; i < 10000; i++) {
            isPrimeOld(i);
        }
        time = System.nanoTime() - time;
        System.out.println(time + " ns (" + time / 1000000 + " ms)");
        time = System.nanoTime();
        for (int i = 2; i < 10000; i++) {
            isPrimeRegex(i);
        }
        time = System.nanoTime() - time;
        System.out.println(time + " ns (" + time / 1000000 + " ms)");
        System.out.println("Done");
    }

    public static boolean isPrimeRegex(int n) {
        return !(new String(new char[n])).matches(".?|(..+?)\\1+");
    }

    public static boolean isPrimeOld(int n) {
        if (n == 2)
            return true;
        if (n < 2)
            return false;
        if ((n & 1) == 0)
            return false;
        int limit = (int) Math.round(Math.sqrt(n));
        for (int i = 3; i <= limit; i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}

このテストでは、2から始めて9,999までの素数であるかどうかを計算します。そして、比較的強力なサーバーでの出力は次のとおりです。

8537795 ns (8 ms)
30842526146 ns (30842 ms)
Done

したがって、数値が十分に大きくなると、非常に非効率になります。（最大999の場合、正規表現は約400ミリ秒で実行されます。）少数の場合は高速ですが、従来の方法で最大99までの素数を生成するよりも、従来の方法で最大9,999までの素数を生成する方が高速です（ 23ミリ秒）。

于 2012-10-03T20:05:42.423 に答える
2

これは、数値が素数であるかどうかをチェックするための実際には効率的な方法ではありません（すべての除数をチェックします）。

効率的な方法は、までの約数をチェックすることsqrt(number)です。これは、数が素数であるかどうかを確認したい場合です。それ以外の場合は、より高速ですが100％正確ではない確率的素数性チェックがあります。

于 2012-10-03T19:51:04.100 に答える