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

128

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?

java  regex  primes 
— Kitlite
źródło
9
@Amir Rachum: !new String(new char[n]).matches(".?|(..+?)\\1+")jest odpowiednikiem !((new String(new char[n])).matches(".?|(..+?)\\1+")).
— Gumbo
14
Jest to nie tylko kosztowne obliczeniowo, ale także potencjalnie niszcząco kosztowne pamięć. Jeśli ktoś zdecyduje się na użycie tego podejścia, którego odradzałbym, ponieważ algorytm znajdowania liczb pierwszych jest tak prosty (po co w świecie komplikować i czynić to tak marnotrawnym), należy sprawdzić przed „nowym char [n ] ”, aby upewnić się, że jest poniżej rozsądnego progu. Np. Wywołaj „prime (Integer.MAX_VALUE)”, a następnie zgłoś błąd, gdy wyrzuca OutOfMemoryError.
— nicerobot
28
@nicerobot: Rozjaśnić się?
— Cam
6
@nicerobot: właściwie to cofam. Początkowo doszedłem do wniosku, że akademicki charakter tego pytania sugeruje użycie go wyłącznie do celów edukacyjnych i że jesteś okropną głupotą. Jednak z drugiej strony tak nie jest; w pytaniu nigdy nie wspomniano ani nawet nie sugerowano, że wyrażenie regularne służy wyłącznie do celów edukacyjnych. W rzeczywistości moje pierwsze wrażenie jest takie, że jest bardzo prosty, jeśli chodzi o fragmenty kodu, więc początkujący może założyć, że można go użyć w praktyce. +1.
— Cam,
7
@incrediman nie martw się. Widzę, jak możesz tak pomyśleć. Moim zamiarem było jedynie ostrzeżenie przed konsekwencjami korzystania z tego, a nie zniechęcanie do uczenia się, jak to działa. Proste „Proszę, nie wdrażaj tego”. przed resztą mojego komentarza mogłoby to uczynić z twojej początkowej perspektywy mniej protekcjonalne brzmienie.
— nicerobot

Odpowiedzi:

119

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).

— Platinum Azure
źródło
10
Wypróbowałem tę logikę z JS w konsoli programistów chrome. na stronie internetowej. i właśnie zdałem 5 do sprawdzenia. Strona się zawiesiła!
— Amogh Talpallikar
Poniższy komentarz daje lepsze wyjaśnienie. Przeczytaj go, zanim przejdziesz dalej!
— Ivan Davidov
„Lepsze” jest subiektywne - powiedziałbym, że podchodzi do problemu z innej strony i jest wspaniałym uzupełnieniem tej odpowiedzi. :-)
— Platinum Azure
1
Właściwie napisałem post na blogu, wyjaśniając to bardziej szczegółowo: Demistyfikacja wyrażenia regularnego, które sprawdza, czy liczba jest pierwsza .
— Illya Gerasymchuk
73

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ż

— smary wielogenowe
źródło
6
+1: Myślę, że twoje podejście jest prawdopodobnie lepsze niż moje. Nie mam pojęcia, dlaczego dostałem tak wiele głosów za lub haczyka ... myślę, że zasługujesz na to bardziej. :-( Przepraszamy
— Platinum Azure
@Platinum: Wow, nigdy bym nie pomyślał, że powiesz to publicznie! Dzięki za wsparcie. Może będę miał [Populist]z tego jakiś dzień.
— smary wielogenowe
2
Cóż, to po prostu prawda (tak jak ją postrzegam) ... naprawdę nie jest to wielka sprawa. Nie jestem tu dla przedstawiciela (chociaż to zawsze bonus i miła niespodzianka) ... Jestem tutaj, aby spróbować odpowiedzieć na pytania, kiedy mogę. Nie powinno więc dziwić, że mogę przyznać, że ktoś zrobił to lepiej niż ja w danym pytaniu.
— Platinum Azure
24

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ą.

— Eyal Schneider
źródło
2
Co dziwne, nawet po wielokrotnym czytaniu innych, dłuższych i bardziej technicznych wyjaśnień, stwierdziłem, że to wyjaśnienie sprawiło, że „kliknęło” w mojej głowie.
— Eight-Bit Guru
2 
/^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 .

— Dinah
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.