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

128

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

public static boolean prime(int n) {
  return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
  • Я не знаю конкретно Java, но понимаю все аспекты этого фрагмента, кроме самого регулярного выражения.
  • У меня есть базовые или базовые знания о Regex, как вы находите его во встроенных функциях PHP.

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

kitlite
источник
9
@Amir Rachum: !new String(new char[n]).matches(".?|(..+?)\\1+")эквивалентно !((new String(new char[n])).matches(".?|(..+?)\\1+")).
Гамбо
14
Это не только дорого с вычислительной точки зрения, но и потенциально чрезвычайно затратно по памяти. Если кто-то решит использовать этот подход, от чего я бы не советовал, поскольку алгоритм поиска простых чисел настолько прост (зачем вообще его усложнять и делать настолько расточительным), то перед "new char [n ] ", чтобы убедиться, что оно ниже разумного порога. Например, вызовите "prime (Integer.MAX_VALUE)", а затем сообщите об ошибке, когда она выдаст OutOfMemoryError.
nicerobot
28
@nicerobot: Расслабься?
Cam
6
@nicerobot: я беру это обратно. Первоначально я полагал, что академический характер этого вопроса подразумевает его использование только в учебных целях, и что вы ведете себя отвратительно. Однако, если подумать, это не так; в вопросе никогда не упоминается и даже не подразумевается, что регулярное выражение предназначено только для учебных целей. На самом деле, мое первое впечатление от этого заключается в том, что он выглядит очень просто с точки зрения фрагментов кода, поэтому новичок действительно может предположить, что его можно использовать на практике. +1.
Cam
7
@incrediman не беспокойся. Я понимаю, как вы могли так подумать. Я только хотел предупредить о последствиях использования этого, а не препятствовать изучению того, как это работает. Простое «Пожалуйста, не развертывайте это». до остальной части моего комментария, возможно, он звучал бы менее снисходительно с вашей первоначальной точки зрения.
nicerobot

Ответы:

120

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

.?

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

(..+?)\\1+

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

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

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

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

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

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

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

Платиновая лазурь
источник
10
Я пробовал эту логику с JS в консоли Chrome dev. на веб-странице. и просто сдал 5 на проверку. Страница разбилась!
Амог Талпалликар,
Комментарий ниже дает лучшее объяснение. Пожалуйста, прочтите его, прежде чем двигаться дальше!
Иван Давыдов
«Лучше» субъективно. Я бы сказал, что он подходит к проблеме с другой стороны и является прекрасным дополнением к этому ответу. :-)
Platinum Azure
1
На самом деле я написал сообщение в блоге, объясняющее это более подробно: Демистификация регулярного выражения, которое проверяет, является ли число простым .
Илья Герасимчук 08
73

Я объясню часть регулярного выражения вне проверки простоты: следующее регулярное выражение, 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является составной, а НЕ простым).
    • Обратите внимание, что модификатор reluctant на ?самом деле не нужен для правильности, но он может помочь ускорить процесс, попробовав 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, НЕ простым

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


Более забавное регулярное выражение

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

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

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

polygenelubricants
источник
6
+1: Я думаю, что ваш подход, вероятно, лучше, чем был мой. Понятия не имею, почему я получил столько голосов или галочки ... Думаю, ты заслуживаешь этого большего. :-( Извините
Platinum Azure
@Platinum: Вау, я бы никогда не подумал, что ты будешь говорить это публично! Спасибо за поддержку. Может быть, я когда-нибудь получу [Populist]от этого.
Полигенные смазки
2
Что ж, это просто правда (как я понимаю) ... на самом деле не так уж и много. Я здесь не для репутации (хотя это всегда бонус и приятный сюрприз) ... Я здесь, чтобы попытаться ответить на вопросы, когда смогу. Таким образом, неудивительно, что я могу признать, что кто-то сделал это лучше, чем я, в конкретном вопросе.
Platinum Azure
25

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

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

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

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

Эяль Шнайдер
источник
2
Как ни странно, даже после неоднократного прочтения других, более длинных и технических объяснений, я обнаружил, что именно это объяснение заставило меня «щелкнуть» в моей голове.
Eight-Bit Guru
2
/^1?$|^(11+?)\1+$/

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

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

Дина
источник