Kann ein regulärer Perl / Java / etc-Ausdruck geschrieben werden, um dezimale (Nicht-) Primzahlen zu vergleichen?

HINWEIS: Diese Regexes wurden für PHP geschrieben und verwenden Possessiv-Quantoren, die in vielen, aber nicht in allen Sprachen verwendet werden, zum Beispiel Java-Skript unterstützt sie nicht. Auch dies ist sehr ineffizient und wird schnell unmöglich werden.

EDIT: hier ist es für die Basis 10 \b(((\d)(?=[\d\s]*({0,10}(n(?=.*n)|nn(?=.*1)|n{3}(?=.*2)|n{4}(?=.*3)|n{5}(?=.*4)|n{6}(?=.*5)|n{7}(?=.*6)|n{8}(?=.*7)|n{9}(?=.*8))?)))+)(?![\d\s]*(n(?=))++(..?1|(...*)+1)) Ich habe danach Base 2 benutzt, um die Dinge einfacher zu machen.

BEARBEITEN: Mit dieser Option können Sie eine Zeichenfolge übergeben, die mehrere Binärzahlen enthält, und mit denen übereinstimmen, die die Primzahl darstellen. \b(((\d)(?=[\d\s]*({0,2}n(?=.*)|{0,2})))+)(?![\d\s]*(n(?=))++(..?1|(...*)+1)) Dies geschieht im Wesentlichen durch die Verwendung von boundary \ b anstelle von string ^, es erlaubt eine beliebige Anzahl von Dezimalen und Leerzeichen, wenn es sich vorwärts zu den ns bewegt, und umschließt den gesamten Teil, der die Basis 1-Darstellungen in einem negativen Look-ahead testet. Abgesehen davon funktioniert es genauso wie das Folgende. Als Beispiel 1111 1011 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn1 passt zu 1011 .

Ich habe es geschafft, etwas zu bekommen, was meiner Meinung nach funktioniert (überprüft auf 25), und es stimmt mit Nicht-Primzahlen überein. Hier ist es für Base 2 (einfacher zu erklären) ^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+\s(n(?=))*+\K(..?1|(..+?)+1) Dies kann bis zur Basis n erweitert werden, aber dies erweitert die Regex sehr schnell. Um diese Regex zum Laufen zu bringen, brauche ich ein paar Voraussetzungen (Ein bisschen Hacky), die Eingabezeichenfolge muss die Zahl gefolgt von einem Leerzeichen sein, gefolgt von mindestens so vielen n Zeichen wie der Wert Ihrer Nummer (wenn Sie die Nummer hatten 10 Sie brauchen mindestens 10 ns danach) gefolgt von den Ziffern Ihrer Basis, ohne Ihre 0-stellig (z. B. für Basis 10 123456789), ohne Ihre 0. Zum Beispiel 11 nnnnnnnnnnnnnn1 . Dies ist aufgrund der Tatsache, dass die Regexes keinen zugänglichen Speicher haben, so dass ich Capturing-Gruppen verwenden muss, um dies zu tun. Schließlich verwendet diese Regex / x, um Leerzeichen im Ausdruck zu ignorieren, streichen Sie den gesamten Platz aus, wenn Sie dies nicht verwenden möchten.

Ich werde jetzt erklären, wie das in drei Schritten funktioniert. Diese Regex funktioniert in 3 Teilen:

Teil 1 : Dieser Teil ändert eine Basis n & gt; 1 zu Basis 1 als einfangende Gruppe von ns

Dies ist der Teil ^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+ , der sehr ähnlich dem Beispiel a^nb^n in der Frage funktioniert. Das ^ an der Front bedeutet, dass das volle Match am Anfang beginnen muss, das ist wichtig für später. Die Hauptstruktur dieses Codes ist ^((\d)(?= \d*\s (suff)))+ Dies nimmt jede Dezimalstelle zwischen dem Anfang und dem ersten Leerzeichen und führt eine positive Vorausschau mit (\ d) (? =) Durch, wobei \ d eine Dezimalzahl und (? =) Ein a ist Vorausschauend ist das \ d in einer einfangenden Gruppe () für später. Es ist die Ziffer, die wir gerade betrachten.

Das Innere des Look-Ahead besteht nicht darin, eine vorausliegende Bedingung zu überprüfen, sondern stattdessen eine Erfassungsgruppe zu erstellen, die unsere Nummer in Basis 1 repräsentiert. Das Innere der Erfassungsgruppe sieht folgendermaßen aus:

Der Teil \ d * \ s bewegt im Grunde die Zeichen, die wir betrachten, um den Rest der verbleibenden Ziffern \ d * (\ d ist Ziffer und * ist 0 bis n so oft wie möglich) zu Beginn des ns.

ist eine selbstreferenzierende Erfassungsgruppe. Hier kommt die Notwendigkeit für die Stellen, die Sie am Ende gesetzt haben. Diese Gruppe passt sich selbst 0 bis 2 Mal an, aber so oft wie möglich (mit \ 3 {0,2} mit \ 3 bedeutet caturing group 3 und {0,2} bedeutet match von 0 bis 2 mal. Dies bedeutet, dass, wenn es eine Zahl vor der aktuellen Ziffer gibt, ihre Basis 1-Darstellung mit 2 multipliziert wird. Dies wäre 10 für die Basis 10 oder 16 für die Basis 16. Wenn dies die erste Ziffer ist, ist die Gruppe undefiniert, so dass sie 0 Mal übereinstimmt. Es fügt dann entweder ein einzelnes n oder kein n hinzu, basierend auf der Übereinstimmung der Ziffer, an der wir gerade arbeiten (unter Verwendung seiner einfangenden Gruppe). Dies geschieht durch einen positiven Blick auf das Ende der Eingabe, wo wir die Ziffern eingeben, n (? =. * \ 2) dies entspricht n, wenn es von der Ziffer, an der wir gerade arbeiten, etwas folgt. Auf diese Weise kann festgestellt werden, an welcher Ziffer wir gerade arbeiten. (Ich hätte einen Blick hinter sich gelassen, aber sie haben feste Länge) Wenn Sie die Basis 3 hatten und prüfen wollten, ob die Zahl, an der Sie gerade arbeiten, 2 ist, würden Sie nn (? =. * 1 \ 2) verwenden, dies würde nn nur dann entsprechen, wenn die Ziffer zwei wäre. Wir haben einen oder Operator '|' für alle diese und wenn keine Ziffer gefunden wird, nehmen wir an, es ist 0 und fügen Sie keine ns hinzu. Da dies in der Erfassungsgruppe ist, wird dieser Abgleich in der Gruppe gespeichert.

Als Zusammenfassung dieses Teils, was wir tun, nehmen Sie jede Ziffer vorausschauend nehmen Sie die Basis 1 Darstellung der vorherigen Ziffern (in der Erfassungsgruppe gespeichert) und multiplizieren Sie es mit der Basis dann passen Sie es, dann fügen Sie die Basis ein Darstellung der Ziffer und speichern Sie sie in der Gruppe. Wenn Sie dies für jede Ziffer nacheinander tun, erhalten Sie eine Basisdarstellung der Zahl. Schauen wir uns und Beispiel an. 101 nnnnnnnnnnnnnnnnnn1

Zuerst geht es wegen ^ auf den Sat. so: 101 nnnnnnnnnnnnnnnnn1

Dann geht es zur ersten Ziffer und speichert es in einem Capturing-Tip 1 01 nnnnnnnnnnnnnnnnn1

Gruppe2: 1

Es verwendet eine Vorausschau mit \ d * \ s, um alle Ziffern und das erste Leerzeichen zu durchlaufen. 1 01 n nnnnnnnnnnnnnnnn1

Es befindet sich jetzt innerhalb der Gruppe 3

Er nimmt den vorherigen Wert dieser Gruppe und passt ihn 0 bis 2 mal an

Da es nicht definiert ist, entspricht es 0 mal.

Es wird nun erneut nach vorne geschaut, um zu versuchen, eine Ziffer zu finden, die der Ziffer in der Erfassungsgruppe 2 entspricht 1 01 n nnnnnnnnnnnnnnnnn 1

wie gefunden wurde, entspricht es 1 n in der Fanggruppe 3 2 1 01 nn nnnnnnnnnnnnnnn1

Es verlässt jetzt Gruppe 3, aktualisiert seinen Wert und lässt den Blick nach vorne Gruppe 3 = n

Nun wird die nächste Ziffer betrachtet und in einer Erfassungsgruppe 1 0 1 nnnnnnnnnnnnnnnnn1

Gruppe 2 = 0

Gruppe 3 = n

Es verwendet dann auch eine Vorausschau und geht zum ersten n 1 0 1 n nnnnnnnnnnnnnnnn1

Es passt dann die Gruppe 3 0 bis 2 Mal an, aber so viele wie möglich, also n 1 0 1 nn nnnnnnnnnnnnnnn1

Es verwendet dann eine Vorausschau, um zu versuchen, die Ziffer in der Gruppe 2 zu vergleichen, die es tun kann, so dass es keine ns hinzufügt, bevor es aus der Gruppe 3 und der Vorausschau

group3 = nn

Es schaut jetzt auf die nächste Ziffer und speichert es in Gruppe 2 10 1 nnnnnnnnnnnnnnnnn1 Mit einem Look-Ahead geht es an den Anfang der ns und passt 2 mal Gruppe 3 10 1 nnnn nnnnnnnnnnnnn1 Es verwendet dann eine Vorausschau, um zu versuchen, die Ziffer in Gruppe 2, die es findet, so zu finden, dass sie mit einem n übereinstimmt und aus der Gruppe 3 und dem Look-Ahead zurückkehrt. group3 = nnnnn Gruppe 3 enthält jetzt die Basis 1-Darstellung unserer Nummer.

Teil 2 Reduziert die Anzahl der ns auf die Größe der Basis 1-Darstellung Ihrer Zahl

Dies entspricht dem Leerzeichen und stimmt dann mit ns überein, solange Sie die Gruppe 3 (die erste Darstellung Ihrer Nummer) vor Ihnen sehen können. Dies geschieht, indem n so oft wie möglich mit einem * + zusammengefügt wird, das Possessiv ist (es lässt einen Matching nicht los, um zu verhindern, dass das Matching später geschrumpft wird, um ein Match zu funktionieren). N hat ein positives Look-Ahead n (? = \ 3) was bedeutet, dass n abgeglichen wird, solange eine Gruppe 3 davor steht (\ 3 gibt Fanggruppe 3). Dies lässt uns mit unserer Basis-1-Repräsentation und den Ziffern, die das einzige sind, was nicht übereinstimmt. Wir haben dann uns \ K sagen lassen, dass das Matching von hier wieder beginnt.

Teil3 Wir verwenden nun den gleichen Algorithmus, der in der Frage erwähnt wird, um Primzahlen zu entfernen, und erzwingen, dass er nicht zwischen dem Beginn der Basis-Repräsentation und dem Anfang der Ziffern übereinstimmt. Sie können lesen, wie das funktioniert Hier Wie zu bestimmen Wenn eine Zahl eine Primzahl mit Regex ist?

Schließlich, um dies zu einem Basis-Regex zu machen, müssen Sie ein paar Dinge tun

faust fügen Sie weitere Ziffern am Ende Ihrer Eingabe-String, dann ändern Sie die n

Ändern Sie abschließend die \ 3 {0,2} in \ 3 {0, n }. wo n die Basis ist. Denken Sie auch daran, dass dies ohne die richtige Eingabe-Zeichenfolge nicht funktioniert.