Jak ustalić, czy liczba jest liczbą pierwszą za pomocą wyrażenia regularnego?

Znalazłem następujący przykład kodu dla Java w RosettaCode :

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

• Nie znam w szczególności Javy, ale rozumiem wszystkie aspekty tego fragmentu z wyjątkiem samego wyrażenia regularnego
• Mam podstawową i zaawansowaną wiedzę o Regex, jaką można znaleźć we wbudowanych funkcjach PHP

Jak wygląda .?|(..+?)\\1+dopasowanie liczb pierwszych?

Powiedziałeś, że rozumiesz tę część, ale dla podkreślenia, wygenerowany String ma długość równą podanej liczbie. Więc ciąg ma trzy znaki wtedy i tylko wtedy, gdy n == 3.

.?

Pierwsza część wyrażenia regularnego mówi „dowolny znak, zero lub jeden raz”. Więc w zasadzie, jest tam zero lub jeden character-- lub, za co już wspomniałem powyżej, n == 0 || n == 1. Jeśli mamy dopasowanie, zwróć negację tego. Odpowiada to temu, że zero i jeden NIE są liczbą pierwszą.

(..+?)\\1+

Druga część wyrażenia regularnego jest nieco trudniejsza i polega na grupach i odwołaniach wstecznych. Grupa to wszystko w nawiasach, które zostanie następnie przechwycone i zapisane przez silnik wyrażeń regularnych do późniejszego wykorzystania. Odwołanie wsteczne to dopasowana grupa, która jest używana później w tym samym wyrażeniu regularnym.

Grupa przejmuje 1 znak, a następnie 1 lub więcej dowolnego znaku. (Znak + oznacza jeden lub więcej, ale TYLKO poprzedniego znaku lub grupy. Więc to nie są „dwa, cztery lub sześć itd. Znaków”, ale raczej „dwa lub trzy itd.” Znak +? Jest podobny do +, ale stara się dopasować jak najmniej znaków. + normalnie próbuje pożreć cały ciąg, jeśli jest to możliwe, co jest złe w tym przypadku, ponieważ uniemożliwia działanie części odniesienia wstecznego.)

Następna część to odwołanie wsteczne: ten sam zestaw znaków (dwa lub więcej), pojawiający się ponownie. Wspomniane odwołanie wsteczne pojawia się raz lub więcej razy.

Więc. Przechwycona grupa odpowiada naturalnej liczbie przechwyconych znaków (od 2 wzwyż). Wspomniana grupa pojawia się wtedy jakąś naturalną liczbę razy (także od 2). Jeśli JEST dopasowanie, oznacza to, że można znaleźć iloczyn dwóch liczb większych lub równych 2, które pasują do ciągu o długości n ... co oznacza, że ​​masz złożone n. Więc ponownie, zwróć negację udanego dopasowania: n NIE jest liczbą pierwszą.

Jeśli nie można znaleźć dopasowania, to nie możesz obliczyć iloczynu dwóch liczb naturalnych większych lub równych 2 ... i masz zarówno niedopasowanie, jak i liczbę pierwszą, stąd ponownie zwrócenie negacji wyniku meczu.

Czy teraz to widzisz? Jest to niewiarygodnie trudne (i kosztowne obliczeniowo!), Ale jednocześnie jest dość proste, gdy już to zrobisz. :-)

Mogę to rozwinąć, jeśli masz dalsze pytania, na przykład o tym, jak faktycznie działa analizowanie wyrażeń regularnych. Ale na razie staram się, aby ta odpowiedź była prosta (lub tak prosta, jak to tylko możliwe).

Wyjaśnię część wyrażenia regularnego poza testowaniem pierwszości: następujący wyrażenie regularne, biorąc pod uwagę a, String sktóre składa się z powtarzania String t, znajduje t.

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

Sposób działania polega na tym, że wyrażenie regularne przechwytuje (.*)do \1, a następnie sprawdza, czy \1+następuje po nim. Korzystanie z ^i$ gwarantuje, że dopasowanie musi obejmować cały ciąg.

Tak więc, w pewnym sensie, otrzymujemy String s, co jest „wielokrotnością” String t, a wyrażenie regularne takie znajdzie t(najdłuższe możliwe, ponieważ \1jest chciwe).

Kiedy zrozumiesz, dlaczego to wyrażenie regularne działa, to (pomijając na razie pierwszą alternatywę w wyrażeniu regularnym OP) wyjaśnienie, w jaki sposób jest używane do testowania pierwszości, jest proste.

• Aby przetestować pierwszorzędność n, najpierw wygeneruj Stringdługość n(wypełnioną tym samymchar )
• Wyrażenie regularne przechwytuje a Stringo pewnej długości (powiedzmy k) do \1i próbuje dopasować \1+do resztyString
  • Jeśli jest dopasowanie, to njest właściwą wielokrotnością ki dlatego nnie jest liczbą pierwszą.
  • Jeśli nie ma dopasowania, to nie kistnieje coś takiego , co dzieli ni ndlatego jest liczbą pierwszą

Jak wygląda .?|(..+?)\1+dopasowanie liczb pierwszych?

Właściwie tak nie jest! To pasuje String , którego długość wynosi NIE prime!

• .?: Pierwsza część naprzemiennych dopasowań Stringdługości 0lub 1(z definicji NIE jest pierwsza)
• (..+?)\1+: Druga część przemienności, odmiana wyrażenia regularnego wyjaśniona powyżej, dopasowania Stringdługości, nktóre są „wielokrotnością” Stringdługości a k >= 2(tj.n Jest złożeniem, a NIE liczbą pierwszą).
  • Zauważ, że niechętny modyfikator w ?rzeczywistości nie jest potrzebny do poprawności, ale może pomóc przyspieszyć proces, próbując knajpierw użyć mniejszego

Zwróć uwagę na ! booleanoperator dopełniacza w returninstrukcji: neguje on matches. Dzieje się tak, gdy wyrażenie regularne NIE pasuje, njest liczbą pierwszą! To logika podwójnie ujemna, więc nic dziwnego, że jest trochę myląca!

Uproszczenie

Oto proste przepisanie kodu, aby był bardziej czytelny:

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

Powyższe jest zasadniczo takie samo, jak oryginalny kod Java, ale podzielone na wiele instrukcji z przypisaniami do zmiennych lokalnych, aby ułatwić zrozumienie logiki.

Możemy również uprościć wyrażenie regularne, używając skończonych powtórzeń, w następujący sposób:

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

Ponownie, biorąc Stringpod uwagę długość n, wypełniony tym samym char,

• .{0,1}sprawdza, czy n = 0,1NIE jest pierwsza
• (.{2,})\1+sprawdza, czy njest poprawną wielokrotnością k >= 2, a nie liczbą pierwszą

Z wyjątkiem niechętnego modyfikatora ?włączonego \1(pominiętego dla przejrzystości), powyższe wyrażenie regularne jest identyczne z oryginałem.

Bardziej zabawne wyrażenie regularne

Poniższe wyrażenie regularne używa podobnej techniki; powinien być edukacyjny:

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

Zobacz też

• Wyrażenia regularne: kto jest bardziej chciwy

Niezła sztuczka regex (choć bardzo nieefektywna) ... :)

Wyrażenie regularne definiuje liczby niebędące liczbami pierwszymi w następujący sposób:

N nie jest liczbą pierwszą wtedy i tylko wtedy, gdy N <= 1 LUB N jest podzielne przez pewne K> 1.

Zamiast przekazywać prostą cyfrową reprezentację N do silnika wyrażeń regularnych, jest on podawany sekwencją o długości N, złożoną z powtarzającego się znaku. Pierwsza część dysjunkcji sprawdza, czy N = 0 lub N = 1, a druga szuka dzielnika K> 1, używając odwołań wstecznych. Zmusza silnik wyrażeń regularnych do znalezienia niepustych sekwencji podrzędnych, które można powtórzyć co najmniej dwa razy, aby utworzyć sekwencję. Jeśli taki podciąg istnieje, to znaczy, że jego długość dzieli N, stąd N nie jest liczbą pierwszą.

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

Zastosuj do liczb po przeliczeniu na podstawę 1 (1 = 1, 2 = 11, 3 = 111, ...). Liczby inne niż liczby pierwsze będą do tego pasować. Jeśli nie pasuje, jest liczbą pierwszą.

Wyjaśnienie tutaj .