Wie kann man feststellen, ob eine Zahl eine Primzahl mit Regex ist?

Ich habe das folgende Codebeispiel für Java auf RosettaCode gefunden :

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

• Ich kenne Java nicht besonders, verstehe aber alle Aspekte dieses Snippets mit Ausnahme des regulären Ausdrucks
• Ich habe grundlegende bis fortgeschrittene Kenntnisse über Regex, wie Sie sie in den integrierten PHP-Funktionen finden

Wie .?|(..+?)\\1+stimmen Primzahlen überein?

Sie sagten, Sie verstehen diesen Teil, aber nur um zu betonen, dass der generierte String eine Länge hat, die der angegebenen Anzahl entspricht. Die Zeichenfolge hat also genau dann drei Zeichen, wenn n == 3.

.?

Der erste Teil der Regex sagt "jedes Zeichen, null oder einmal". Also im Grunde gibt es keine oder eine character-- oder, je , was ich oben erwähnt, n == 0 || n == 1. Wenn wir die Übereinstimmung haben, geben Sie die Negation davon zurück. Dies entspricht der Tatsache, dass Null und Eins NICHT Primzahl sind.

(..+?)\\1+

Der zweite Teil der Regex ist etwas kniffliger und basiert auf Gruppen und Rückreferenzen. Eine Gruppe ist alles in Klammern, was dann erfasst und von der Regex-Engine zur späteren Verwendung gespeichert wird. Eine Rückreferenz ist eine übereinstimmende Gruppe, die später in derselben Regex verwendet wird.

Die Gruppe erfasst 1 Zeichen und dann 1 oder mehr Zeichen. (Das + Zeichen bedeutet ein oder mehrere, aber NUR das vorherige Zeichen oder die vorherige Gruppe. Dies sind also nicht "zwei oder vier oder sechs usw. Zeichen", sondern "zwei oder drei usw.". Das +? Ist wie +, aber Es wird versucht, so wenig Zeichen wie möglich zuzuordnen. + versucht normalerweise, die gesamte Zeichenfolge zu verschlingen, wenn dies möglich ist. Dies ist in diesem Fall schlecht, da der Backreference-Teil nicht funktioniert.)

Der nächste Teil ist die Rückreferenz: Derselbe Zeichensatz (zwei oder mehr), der erneut angezeigt wird. Diese Rückreferenz erscheint ein- oder mehrmals.

So. Die erfasste Gruppe entspricht einer natürlichen Anzahl von erfassten Zeichen (ab 2). Diese Gruppe erscheint dann einige natürliche Male (auch ab 2). Wenn es eine Übereinstimmung gibt, bedeutet dies, dass es möglich ist, ein Produkt mit zwei Zahlen größer oder gleich 2 zu finden, die mit der Zeichenfolge mit der Länge n übereinstimmen ... was bedeutet, dass Sie ein zusammengesetztes n haben. Geben Sie also erneut die Negation des erfolgreichen Spiels zurück: n ist NICHT Primzahl.

Wenn keine Übereinstimmung gefunden werden kann, können Sie kein Produkt mit zwei natürlichen Zahlen größer oder gleich 2 finden ... und Sie haben sowohl eine Nichtübereinstimmung als auch eine Primzahl, daher wieder die Rückkehr der Negation des Spielergebnisses.

Siehst du es jetzt Es ist unglaublich knifflig (und rechenintensiv!), Aber gleichzeitig ist es auch ziemlich einfach, sobald Sie es bekommen. :-)

Ich kann näher darauf eingehen, wenn Sie weitere Fragen haben, z. B. wie die Regex-Analyse tatsächlich funktioniert. Aber ich versuche, diese Antwort vorerst einfach zu halten (oder so einfach wie es nur sein kann).

Ich werde den Regex-Teil außerhalb des Primalitätstests erklären: Der folgende Regex, der a gegeben ist String sund aus Wiederholungen besteht String t, findet t.

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

Das System funktioniert so , dass die Regex Aufnahmen (.*)in \1und sieht dann , wenn es \1+danach. Die Verwendung von ^und $stellt sicher, dass eine Übereinstimmung mit der gesamten Zeichenfolge bestehen muss.

In gewisser Weise erhalten wir String salso ein "Vielfaches" von String t, und der Regex wird ein solches finden t(das längste, da \1es gierig ist).

Sobald Sie verstanden haben, warum dieser reguläre Ausdruck funktioniert, ist es einfach, die erste Alternative im regulären Ausdruck des OP zu ignorieren und zu erklären, wie er für Primalitätstests verwendet wird.

• Um die Primalität von zu testen n, generieren Sie zuerst eine StringLänge n(gefüllt mit derselben char).
• Der Regex erfasst eine StringLänge von (sagen wir k) in \1und versucht, \1+mit dem Rest des zu übereinstimmenString
  • Wenn es eine Übereinstimmung gibt, dann nist ein richtiges Vielfaches von kund ist daher nkeine Primzahl.
  • Wenn es keine Übereinstimmung gibt, gibt es keine solche k, die sich teilt nund ndaher eine Primzahl ist

Wie .?|(..+?)\1+stimmen Primzahlen überein?

Eigentlich nicht! Es passt zu String dessen Länge NICHT prim ist!

• .?: Der erste Teil des Wechsels entspricht Stringder Länge 0oder 1(per Definition NICHT prim)
• (..+?)\1+: Der zweite Teil des Wechsels, eine Variation des oben erläuterten regulären Ausdrucks, entspricht Stringeiner Länge n, die "ein Vielfaches" einer StringLänge ist k >= 2(dh neine zusammengesetzte, keine Primzahl).
  • Beachten Sie, dass das nur ungern Modifikator ?ist eigentlich nicht für Richtigkeit benötigt, aber es kann beschleunigen den Prozess helfen , indem sie kleinere versuchen kzuerst

Beachten Sie den ! booleanKomplementoperator in der returnAnweisung: Er negiert den matches. Es ist, wenn der Regex NICHT übereinstimmt, nist Prime! Es ist eine doppelt negative Logik, also kein Wunder, dass es irgendwie verwirrend ist !!

Vereinfachung

Hier ist eine einfache Neufassung des Codes, um ihn besser lesbar zu machen:

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

Das Obige ist im Wesentlichen dasselbe wie der ursprüngliche Java-Code, jedoch in mehrere Anweisungen mit Zuweisungen zu lokalen Variablen unterteilt, um das Verständnis der Logik zu erleichtern.

Wir können den regulären Ausdruck auch durch endliche Wiederholung wie folgt vereinfachen:

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

Wieder gegeben, gegeben von einer StringLänge n, gefüllt mit dem gleichen char,

• .{0,1}prüft ob n = 0,1, NICHT grundieren
• (.{2,})\1+prüft, ob nes sich um ein richtiges Vielfaches von handelt k >= 2, NICHT um eine Primzahl

Mit Ausnahme des nur ungern Modifikator ?auf \1(aus Gründen der Übersichtlichkeit weggelassen), ist die obige regex identisch mit dem Original.

Mehr Spaß Regex

Der folgende reguläre Ausdruck verwendet eine ähnliche Technik. es sollte lehrreich sein:

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

Siehe auch

• Reguläre Ausdrücke: Wer ist gieriger?

Netter Regex-Trick (obwohl sehr ineffizient) ... :)

Der Regex definiert Nicht-Primzahlen wie folgt:

N ist nicht genau dann eine Primzahl, wenn N <= 1 ODER N durch etwas K> 1 teilbar ist.

Anstatt die einfache digitale Darstellung von N an die Regex-Engine zu übergeben, wird sie mit einer Folge der Länge N gespeist , die aus einem sich wiederholenden Zeichen besteht. Der erste Teil der Disjunktion prüft auf N = 0 oder N = 1, und der zweite Teil sucht unter Verwendung von Rückreferenzen nach einem Divisor K> 1. Es zwingt die Regex-Engine, eine nicht leere Teilsequenz zu finden, die mindestens zweimal wiederholt werden kann, um die Sequenz zu bilden. Wenn eine solche Teilsequenz existiert, bedeutet dies, dass ihre Länge N teilt, daher ist N keine Primzahl.

/^1?$|^(11+?)\1+$/

Nach der Umrechnung auf Basis 1 auf Zahlen anwenden (1 = 1, 2 = 11, 3 = 111, ...). Nicht-Primzahlen werden dem entsprechen. Wenn es nicht passt, ist es Prime.

Erklärung hier .