Primzahlen mit RegEx bestimmen (the nerdy way)

Heute habe ich bei Noulakaz einen sehr verwirrenden Weg gefunden eine Zahl auf eine Primzahl hin zu prüfen. Also ob zum Beispiel die 101 eine Primzahl ist… (ist sie ;)). Dazu gibt es einen sehr trickreichen RegEx Ausdruck.

In Perl Syntax sieht das dann so aus:

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

Das musste ich natürlich direkt mal testen und habe es in Java (In Java muss man den extra Backslash (\) beachten!) umgesetzt:

import java.util.regex.Pattern;
 
public class TestPrime {
 
        public TestPrime(int n) {
 
                System.out.println(n + " ist " + (checkPrime(n) ? "keine" : "eine")
                                + " Primzahl");
 
        }
 
        private boolean checkPrime(int n) {
 
                String s = "";
                for (int i = 0; i < n; i++)
                        s += 1;
                return (Pattern.compile("^1?$|^(11+?)\\1+$").matcher(s)).matches();
 
        }
 
        public static void main(String[] args) {
 
                new TestPrime(100001);
 
        }
 
}

Und siehe da, es funktioniert! :D
Erstaunlich aber wahr, wenn auch sehr sehr sehr (!) langsam. Es funktioniert nämlich wie folgt:

1. Aus der eingegebenen Zahl, zum Beispiel 7, wird ein String aus Einsen erstellt und zwar so viele Einsen wie der Betrag der Zahl vorher, also würde bei 7 der String 1111111 lauten.
2. Dieser wird dann mit dem regulären Ausdruck geprüft, stimmt er überein, wird also true zurückgeliefert, ist die Zahl keine Primzahl, passt der Ausdruck nicht, ist es Eine.

Klingt verrückt, klappt aber, denn der reguläre Ausdruck besteht grob aus zwei Teilen, der erste Teil ^1?$ prüft, ob der String aus einer oder keiner Eins besteht, so wird die 0 oder die 1 abgefangen, beides per Definition keine Primzahlen. Dann folgt der zweite Teil ^(11+?)\\1+$. Der ist etwas tricky. Und zwar wird hier (^(11+?)) geprüft ob eine 1, gefolgt von mindestens einer weiteren 1 auftaucht. Wenn ja, wird dieser in die Backreference Variable \1 geschrieben, die danach folgt.

Am Beispiel der 7:

7 entspricht 1111111 in Einsen ausgeschrieben, der erste Teil trifft nicht zu, es sind mehrere Ziffern, also wird durch das Oder-Zeichen | der zweite Teil geprüft. Zuerst ob ^(11+?) zutrifft, ja, tut es, jedoch trifft \1+$ nicht zu, denn es bleiben 5 Ziffern übrig. Jetzt macht die RegEx-Engine einen Backtrack und matcht (11+?) mit 111. \1+$ ist jetzt aber 111, es bleiben jedoch 4 Ziffern übrig, es passt also wieder nicht… etc. Am Ende passt 1111111 gar nicht auf den regulären Ausdruck, es ist also eine Primzahl. Und das stimmt ja auch! Erstaunlich :).

Das war jetzt sicher etwas kompliziert, aber im Grunde genommen wird einfach getestet ob es eine gerade oder ungerade Zahl ist, bei einer geraden ist direkt Schluss, bei einer ungeraden wird einfach mit jeder möglichen Zahl von 3 an multipliziert und getestet ob es ein Teiler der Zahl ist. Wenn ja dann ist es keine Primzahl, wenn nicht ist es eine. Sehr nerdy, ich weiß, aber die Idee an sich ist sehr geil finde ich :D.

Nur wie gesagt sehr sehr langsam… Durch den riesigen String (bei großen Zahlen) und das ganze backtracken der RegEx Engine geht ziemlich viel CPU Zeit drauf. An einem P4 mit 3 GHz und 2 GB Ram dauerte das Testen der Zahl 10789 mehere Minuten. Das ist natürlich daher keine Lösung neue Primzahlen zu finden, sondern eher ein Proof of Concept für tolle reguläre Ausdrücke :).

In Java etwas aufgebläht, in Ruby aber zum Beispiel sehr schlank, siehe Lösung von Noulakaz:

Avinash@noulakaz:~$ irb
irb(main):001:0> def is_prime(n)
irb(main):002:1> ("1" * n) !~ /^1?$|^(11+?)\1+$/
irb(main):003:1> end
=> nil
irb(main):004:0> is_prime(10)
=> false
irb(main):005:0> is_prime(11)
=> true
irb(main):006:0> is_prime(12)
=> false
irb(main):007:0> is_prime(13)
=> true
irb(main):008:0> is_prime(99)
=> false
irb(main):009:0> is_prime(100)
=> false
irb(main):010:0> is_prime(101)
=> true