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

Я объясню часть регулярного выражения вне проверки простоты: следующее регулярное выражение, учитывая String s , которое состоит из повторения Строка 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+ остальным. строки
  • Если есть совпадение, то n является правильным кратным k , и, следовательно, n не является простым.
  • Если совпадений нет, то не существует такого k , которое делит n , и n , следовательно, является простым

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

На самом деле это не так! Он соответствует Строке , длина которой НЕ является простой!

• .? : первая часть чередования соответствует Строке длины 0 или 1 (НЕ простое число по определению)
• ( ..+?) \ 1+ : вторая часть чередования, вариант регулярного выражения, описанного выше, соответствует Строке длины n , которая «кратна» Строка длины k> = 2 (т.е. n является составным, а НЕ простым числом).
  • Обратите внимание, что модификатор сопротивления ? на самом деле не нужен для правильности, но он может помочь ускорить процесс, попробовав сначала меньшее k

Обратите внимание на ! логический оператор дополнения в операторе return : он отменяет совпадения . Это когда регулярное выражение НЕ соответствует , 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!"

См. также

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

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

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

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

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

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

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

Explanation here.