Как определить, является ли число простым с регулярным выражением?

я объясню часть регулярного выражения за пределами тестирования примитивности: следующее регулярное выражение, учитывая String s который состоит из повторения String t находит t.

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

как это работает, что регулярное выражение захватывает (.*) на , а потом видит, есть ли + следуя за ним. Используя ^ и $ гарантирует, что совпадение должно быть всей строки.

так что, в некотором смысле, нам дали String s, который является "кратным"String t, и регулярное выражение найду таких t (как можно дольше, так как жадный).

как только вы поймете, почему это регулярное выражение работает, то (игнорируя первый альтернативный вариант в регулярном выражении OP на данный момент) объясняя, как он используется для тестирования примитивности, просто.

• чтобы проверить примитивность n сначала нужно создать String длиной n (заполненный тем же char)
• регулярное выражение захватывает a String некоторой длины (скажем k) в , и старается чтобы соответствовать + остальное String
  • если есть совпадение, то n является правильным кратным k, и поэтому n не премьер.
  • если нет совпадения, то нет такого k существует то, что делит n и главный

---

как .?|(..+?)+ простые числа матч?

на самом деле, это не так! Это игр String чья длина не является простой!

• .?: первая часть чередования соответствует String длиной 0 или 1 (не простой по определению)
• (..+?)+: вторая часть чередования, вариация регулярного выражения, объясненного выше, соответствует String длиной n это "кратное" a String длиной k >= 2 (т. е. n является составным, а не простым).
  • обратите внимание, что неохотно модификатор ? на самом деле не требуется для корректности, но это может помочь ускорить процесс, пытаясь меньше k первый

Примечание !boolean оператор дополнения в return заявление: это отрицает matches. Это когда регулярное выражение НЕ матч n премьер! Это двойная отрицательная логика, поэтому неудивительно, что это сбивает с толку!!

---

упрощение

вот простой переписывание кода, чтобы сделать его более читабельным:

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

вышеизложенное по существу совпадает с исходным кодом Java, но разбито на несколько операторов с назначениями локальным переменным, чтобы сделать логику более понятной.

мы также можем упростить выражение, используя конечное повторение, следующим образом:

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

опять дали String длиной n, заполненный тем же char,

• .{0,1} проверяет если n = 0,1, а не премьер -
• (.{2,})+ проверяет, является ли n является правильным кратным k >= 2, а не премьер -

за исключением неохотного модификатора ? on (опущено для ясности), приведенное выше регулярное выражение идентично оригиналу.

---

больше удовольствия регулярное выражение

следующее регулярное выражение использует аналогичную технику; оно должно быть образовательным:

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

посмотреть также

• регулярные выражения: кто жаднее

хороший трюк с регулярным выражением (хотя и очень неэффективный)... :)

регулярное выражение определяет не простые числа следующим образом:

N не является простым тогда и только тогда, когда N1.

вместо того, чтобы передавать простое цифровое представление N в механизм регулярных выражений, он подается с последовательностью длина N, состоящий из повторяющегося символа. Первая часть дизъюнкции проверяет наличие N=0 или N=1, а вторая ищет делитель K>1, используя обратная ссылка. Это заставляет механизм регулярных выражений найти некоторую непустую подпоследовательность, которая может быть повторена по крайней мере дважды, чтобы сформировать последовательность. Если такая подпоследовательность существует, это означает, что ее длина делит N, следовательно N не является простым числом.

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

применить к числам после преобразования базы 1 (1=1, 2=11, 3=111, ...). Не простые числа будут соответствовать этому. Если он не совпадает,то это просто.

объяснение здесь.