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

Question

Я нашел следующий пример кода для Java на RosettaCode:

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

• Я не знаю Java в частности, но понимаю все аспекты этого фрагмента, за исключением самого регулярного выражения
• У меня есть базовые или базовые знания Regex, которые вы найдете во встроенных функциях PHP

Как .?|(..+?)\\1+ сопоставить простые числа?

Answer 1

Вы сказали, что понимаете эту часть, но только для того, чтобы подчеркнуть, сгенерированная строка имеет длину, равную предоставленному числу. Таким образом, строка имеет три символа, если и только если n == 3,

.?

Первая часть регулярного выражения говорит: "любой символ, ноль или один раз". Итак, в основном, есть ноль или один символ - или, как я уже говорил выше, n == 0 || n == 1, Если у нас есть совпадение, верните отрицание этого. Это соответствует тому факту, что ноль и единица НЕ являются простыми.

(..+?)\\1+

Вторая часть регулярного выражения немного сложнее, опираясь на группы и обратные ссылки. Группа - это что-нибудь в скобках, которое затем будет захвачено и сохранено механизмом регулярных выражений для последующего использования. Обратная ссылка - это сопоставленная группа, которая позже используется в том же регулярном выражении.

Группа захватывает 1 символ, а затем 1 или более символов. (Символ + означает один или несколько, но ТОЛЬКО предыдущего символа или группы. Так что это не "два, четыре или шесть символов и т. Д.", А скорее "два или три и т. Д.". он пытается сопоставить как можно меньше символов. + обычно пытается поглотить всю строку, если это возможно, что плохо в этом случае, потому что это препятствует работе обратной ссылки.)

Следующая часть - обратная ссылка: тот же набор символов (два или более), появляющийся снова. Указанная обратная ссылка появляется один или несколько раз.

Так. Захваченная группа соответствует натуральному количеству захваченных символов (от 2 и далее). Затем указанная группа появляется некоторое натуральное число раз (также начиная с 2). Если есть соответствие, это означает, что можно найти произведение двух чисел, больших или равных 2, которые соответствуют строке длины n... то есть у вас есть составное число n. Итак, еще раз, верните отрицание успешного совпадения: n НЕ простое число.

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

Вы видите это сейчас? Это невероятно сложно (и вычислительно дорого!), Но в то же время это довольно просто, как только вы его получите.:-)

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

Answer 2

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

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

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

Таким образом, в некотором смысле, мы получили String s, который является "кратным" из String tи регулярное выражение найдет такой t (максимально долго, так как \1 жадный).

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

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

---

Как .?|(..+?)\1+ сопоставить простые числа?

На самом деле это не так! Это соответствует String чья длина НЕ проста!

• .?: Первая часть чередования матчей String длины 0 или же 1 (НЕ простой по определению)
• (..+?)\1+: Вторая часть чередования, разновидность регулярного выражения, объясненного выше, совпадает String длины n это "кратный" 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,})\1+ проверяет, если n является правильным кратным k >= 2, НЕ премьер

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

---

Больше веселья, регулярное выражение

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

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

Смотрите также

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

Answer 3

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

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

N не простое тогда и только тогда, когда N<=1 ИЛИ N делится на некоторое K>1.

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

Answer 4

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

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

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