134

RosettaCodeで Java の次のコード例を見つけました。

public static boolean prime(int n) {
  return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
  • 私は特にJavaを知りませんが、正規表現自体を除いて、このスニペットのすべての側面を理解しています
  • 組み込みの PHP 関数で見られるように、Regex の基本的な知識から高度な知識まで持っています。

.?|(..+?)\\1+素数はどのように一致しますか?

4

4 に答える 4

121

あなたはこの部分を理解していると言いましたが、強調するために、生成された文字列の長さは指定された数と同じです。したがって、文字列は の場合に限り 3 文字になりますn == 3。

.?

正規表現の最初の部分は、「任意の文字、0 回または 1 回」です。つまり、基本的に、文字は 0 か 1 か、または、前述のようにn == 0 || n == 1. 一致する場合は、その否定を返します。これは、0 と 1 が素数でないことと一致します。

(..+?)\\1+

正規表現の 2 番目の部分は少しトリッキーで、グループと後方参照に依存しています。グループは括弧内のすべてであり、後で使用するために正規表現エンジンによってキャプチャおよび保存されます。後方参照は、後で同じ正規表現で使用される一致したグループです。

グループは 1 人のキャラクターを捕獲し、次に任意の 1 人以上のキャラクターを捕獲します。(+ 文字は 1 つ以上を意味しますが、前の文字またはグループのみを意味します。したがって、これは「2 つまたは 4 つまたは 6 つなどの文字」ではなく、「2 つまたは 3 つなど」です。+? は + に似ていますが、 + 通常は可能な限り文字列全体を取り込もうとしますが、これは後方参照部分が機能しなくなるため、この場合は悪いことです。)

次の部分は後方参照です。同じ文字セット (2 つ以上) が再び表示されます。この後方参照は 1 回以上表示されます。

そう。キャプチャされたグループは、キャプチャされた文字の自然な数 (2 以降) に対応します。このグループは自然な回数出現します (これも 2 以降)。一致する場合、これは、長さ n の文字列に一致する 2 以上の 2 つの数値の積を見つけることができることを意味します...つまり、複合 n があることを意味します。繰り返しますが、成功した一致の否定を返します: n は素数ではありません。

一致するものが見つからない場合、2 以上の 2 つの自然数の積を考え出すことはできません...そして、不一致と素数の両方があるため、再び否定が返されます試合結果の。

今見えますか？信じられないほどトリッキーです (そして、計算コストも高くなります!) が、一度理解すれば、同時に簡単でもあります。:-)

正規表現の解析が実際にどのように機能するかなど、さらに質問がある場合は詳しく説明できます。しかし、私は今のところ、この答えをシンプルにしようとしています (または可能な限りシンプルに)。

于 2010-05-08T18:10:44.640 に答える
73

素数性テスト以外の正規表現部分について説明します。次の正規表現String sは、 の繰り返しで構成されるa を指定するとString t、 が見つかりtます。

    System.out.println(
        "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1")
    ); // prints "Mamamia"

それが機能する方法は、正規表現が にキャプチャ(.*)し\1、それを\1+フォローしているかどうかを確認することです。and を使用する^と$、文字列全体が一致する必要があります。

したがって、ある意味でString sは、 の「倍数」である が与えられ、String t正規表現はそのようなものを見つけますt(貪欲なので、可能な限り最長\1)。

この正規表現が機能する理由を理解したら、(今のところ OP の正規表現の最初の代替を無視して) 素数テストにどのように使用されるかを説明するのは簡単です。

  • の素数性をテストするには、まず長さの をn生成します(同じ で埋められます)Stringnchar
  • 正規表現はString、ある長さ (たとえばk) を にキャプチャし、残りの部分と\1一致させようとします。\1+String
    • 一致する場合、nは の固有倍数であるkため、n素数ではありません。
    • 一致するものがない場合、 を割るようなものkは存在しないため、素数です。nn

.?|(..+?)\1+素数はどのように一致しますか?

実際、そうではありません！長さが素数でないものと一致します! String

  • .?String:長さ0orの交互一致の最初の部分1(定義により素数ではない)
  • (..+?)\1+: 代替の 2 番目の部分は、上記で説明した正規表現のバリエーションであり、長さの「倍数」である長さの一致(つまりString、合成であり、素数ではありません)。 nStringk >= 2n
    • reluctant 修飾子は正確さのために実際には必要ないことに注意してください?。k

! booleanステートメントの補数演算子に注意してください。これは .returnを否定しmatchesます。それは、正規表現が一致しないnときです。二重負論理なので、ややこしいのも無理はないですよね!!

簡素化

読みやすくするためにコードを簡単に書き直すと、次のようになります。

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

上記は基本的に元の Java コードと同じですが、ロジックを理解しやすくするために、ローカル変数への割り当てを含む複数のステートメントに分割されています。

次のように、有限反復を使用して正規表現を単純化することもできます。

boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+");

繰り返しますが、与えられたString長さn、同じで満たされたchar、

  • .{0,1}かどうかを調べますn = 0,1。素数ではない
  • (.{2,})\1+が素数nではなく の適切な倍数かどうか調べますk >= 2

?reluctant 修飾子on (わかりやすくするために省略) を除いて\1、上記の正規表現は元の正規表現と同じです。

もっと楽しい正規表現

次の正規表現は、同様の手法を使用しています。それは教育的であるべきです：

System.out.println(
    "OhMyGod=MyMyMyOhGodOhGodOhGod"
        .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!")
); // prints "Oh! My! God!"

こちらもご覧ください

于 2010-05-08T18:19:23.790 に答える
27

素敵な正規表現のトリック (非常に非効率的ですが)... :)

正規表現は、非素数を次のように定義します。

N<=1 または N が K>1 で割り切れる場合に限り、N は素数ではありません。

N の単純なデジタル表現を正規表現エンジンに渡す代わりに、繰り返し文字で構成される長さN のシーケンスが供給されます。選言の最初の部分は N=0 または N=1 をチェックし、2 番目の部分は後方参照を使用して除数 K>1 を探します。正規表現エンジンに、シーケンスを形成するために少なくとも 2 回繰り返すことができる空でないサブシーケンスを見つけるように強制します。そのようなサブシーケンスが存在する場合、それはその長さが N を分割することを意味し、したがって N は素数ではありません。

于 2010-05-08T18:48:10.207 に答える
2 
/^1?$|^(11+?)\1+$/

1を底に変換した後の数値に適用します（1 = 1、2 = 11、3 = 111、...）。非素数はこれに一致します。一致しない場合は素数です。

ここでの説明。

于 2010-07-21T17:21:20.300 に答える