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

Ответ 1

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

.?

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

(..+?)\\1+

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

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

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

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

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

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

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

Ответ 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 сначала создайте a String длины n (заполненной тем же char)
• Регулярное выражение захватывает String некоторой длины (скажем k) в \1 и пытается сопоставить \1+ с остальной частью String
  • Если существует совпадение, то n является правильным кратным k, и поэтому n не является простым.
  • Если нет совпадения, тогда нет такого k, который делит n, а n является, таким образом, простым

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

Собственно, это не так! Он matches 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+");

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

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

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

Более веселое выражение

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

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

См. также

• Регулярные выражения: who greedier

Ответ 3

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

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

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

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

Ответ 4

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

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

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