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

Wyjaśnię część regex poza testowaniem primality: następujące regex, biorąc pod uwagę String s, któ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 regex przechwytuje (.*) do \1, a następnie widzi, czy \1+ podąża za nim. Użycie ^ i $ zapewnia, że dopasowanie musi być całego ciągu znaków.

Więc w pewnym sensie otrzymujemy String s, która jest "wielokrotnością" String t, a regex znajdzie takie t (najdłuższe możliwe, ponieważ \1 jest chciwy).

Gdy zrozumiesz, dlaczego to wyrażenie regularne działa ,to (ignorując na razie pierwszy wariant w wyrażeniu regularnym op) wyjaśnienie, w jaki sposób jest używane do testowania primality jest proste.

Aby sprawdzić pierwotność n, najpierw Wygeneruj String o długości n (wypełnioną tym samym char)
• regex przechwytuje String pewnej długości (powiedzmy k) do \1 i próbuje dopasować \1+ do reszty String
  • jeśli istnieje dopasowanie, to n jest właściwym wielokrotność k, a zatem n nie jest liczbą pierwszą.
  Jeśli nie ma dopasowania, to nie istnieje taka k, która dzieli n, A n jest zatem liczbą pierwszą

Jak .?|(..+?)\1+ pasuje do liczb pierwszych?

• .?: pierwsza część alternacji pasuje String o długości 0 lub 1 (nie pierwsza przez definicja)
• (..+?)\1+ : druga część alternacji, odmiana regex wyjaśniona powyżej, pasuje String o długości n, która jest "wielokrotnością" String o długości k >= 2 (tzn. n jest złożoną, Nie pierwszą).
  • zauważ, że niechętny modyfikator ? w rzeczywistości nie jest potrzebny do poprawności, ale może przyspieszyć proces, próbując najpierw mniejszych k {70]}

Uwaga ! boolean operator dopełniacza w return twierdzenie: neguje matches. Gdy regex nie pasuje, n jest liczbą pierwszą! To logika podwójnie negatywna, więc nic dziwnego, że to trochę mylące!!

Uproszczenie

Oto proste przepisanie kodu, aby uczynić go bardziej czytelnym:

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

Powyższy kod jest zasadniczo taki sam jak oryginalny kod Javy, ale podzielony na wiele instrukcji z przypisaniem do zmiennych lokalnych, aby logika była łatwiejsza do zrozumienia.

We można również uprościć wyrażenia 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 pod uwagę String o długości n, wypełniony tym samym char,

• .{0,1} sprawdza, czy n = 0,1, a nie prime
• (.{2,})\1+ sprawdza, czy n jest właściwą wielokrotnością k >= 2, A Nie liczbą pierwszą

Z wyjątkiem niechętnego modyfikatora ? on \1 (pominięty dla jasności), powyższy regex jest identyczny z oryginałem.

More fun regex

The po regex 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

Ładny trik regex (choć bardzo nieefektywny)... :)

Regex definiuje Nie-liczby pierwsze w następujący sposób:

N nie jest liczbą pierwszą wtedy i tylko wtedy, gdy N 1.

Zamiast przekazywać prostą cyfrową reprezentację n do silnika regex, jest ona zasilana sekwencją 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 backreferences. Zmusza do regex engine, aby znaleźć pewną niepustą pod sekwencję, która może być powtórzona co najmniej dwa razy w celu utworzenia sekwencji. Jeśli taka podklasa istnieje, oznacza to, że jej długość dzieli N, A więc N nie jest liczbą pierwszą.

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

Zastosuj do liczb po przeliczaniu na bazę 1 (1=1, 2=11, 3=111, ...). Nie-pierwsze będą pasować do tego. Jeśli nie pasuje, to jest pierwsza.

Wyjaśnienie tutaj .