Введение

Как-то я исследовал способы наиболее эффективного определения простоты числа и наткнулся на следующий код:

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

Он меня заинтриговал. Хоть это, возможно, и не самый эффективный способ, но определённо один из наименее очевидных, поэтому мне стало любопытно. Каким образом соответствие регулярному выражению .?|(..+?)\1+ должно показать, что число непростое (после его преобразования в унарную систему счисления)?

Если вы заинтересовались, продолжайте чтение, я проанализирую это регулярное выражение и объясню, что же в нём происходит. Объяснение не зависит от языка программирования, однако я приведу версии показанного выше Java-кода на Python, JavaScript и Perl  и объясню, почему они немного различаются.

Я объясню, как регулярное выражение ^.?$|^(..+?)\1+$ способно отфильтровывать все простые числа. Почему это выражение, а не .?|(..+?)\1+ (использованное в примере кода на Java)? Это связано с тем, как работает String.matches(), о чём я расскажу ниже.

Хотя по этой теме есть несколько постов, я считаю, что они недостаточно глубоки и в них приводится лишь высокоуровневое объяснение, недостаточно хорошо излагающее важные подробности. В своей статье я попытаюсь объяснить подробности, чтобы их мог понять любой. Моя цель — сделать этот код понятным каждому, будь вы гуру регулярных выражений или впервые о них услышали.

1. Простые числа и регулярные выражения — теория

Давайте начнём с высокого уровня. Но для начала нужно убедиться, что все понимают определения. Если вы знаете, что такое простое число и знакомы с регулярными выражениями, то можете сразу перейти к разделу 2. Я постараюсь объяснить подробно, как работают все части регулярного выражения, чтобы могли понять даже не знающие их читатели.

Простые числа

Во-первых, простое число — это любое натуральное число больше 1, без остатка делящееся только на 1 и на само себя. Вот список первых 8 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19. Например, 5 простое, потому что без остатка оно делится только на 1  и 5. Да, его можно поделить на 2, но это даст остаток 1, так как 5 = 2*2 + 1. Число 4 непростое (составное), потому что его можно поделить без остатка на  1, 2 и 4.

Регулярные выражения

Хорошо, а теперь перейдём к синтаксису регулярных выражений (regex). Существует достаточно большое количество различных стилей, я не буду делать упор на какой-то конкретный, потому что смысл поста не в этом. Описанные в нём концепции работают схожим образом для всех наиболее распространённых стилей, поэтому можно об этом не волноваться. Если хотите больше узнать о регулярных выражениях, то сходите на Regular-Expressions.info, это отличный ресурс для изучения regex и справочник по ним.

Вот шпаргалка с концепциями, которые будут необходимы для дальнейших объяснений:

• ^ — соответствуют позиции до первого символа в строке;

• $ — соответствует позиции сразу после последнего символа в строке;

• . — соответствует любому символу, за исключением символов разрыва строки (например, не соответствует \n);

• | — соответствует всему, что находится слева или справа от него. Можно представить, что это оператор or.

• ( и ) — ограничители группы. Поместив часть регулярного выражения в скобки, мы группируем эту часть регулярного выражения. Это позволяет нам применять квантификаторы (наподобие +) к целой группе или ограничить чередование (например, «or»: |) частью регулярного выражения. Кроме того, скобки создают нумерованные группы, к которым можно обращаться позже при помощи обратных ссылок (подробнее об этом ниже);

• \<здесь_число> — обратные ссылки (backreference) соответствуют тому же тексту, что и ранее соответствовавший группе. <здесь_число> — это номер группы (выше мы говорили, что скобки создают нумерованные группы, вот здесь они нам и пригождаются). Чтобы стало чуть понятнее, я приведу пример, так что не теряйтесь!

• + — соответствует предшествующему токену (например, это может быть символ или группа символов, если предшествующий токен — это группа) один или несколько раз;

• * — соответствует предшествующему токену ноль или более раз;

• если ? используется после квантификаторов + или *, то он делает квантификатор нежадным (подробности ниже).

Группы и обратные ссылки

Как и обещал, объясню, как совместно работают группы и обратные ссылки.

Мы говорили, что скобки создают нумерованные группы. Что имеется в виду? Это значит, что когда мы используем скобки, создаётся группа, соответствующая каким-то символам, и мы можем позже ссылаться на эти соответствующие символы. Номера присваиваются группам в том порядке, в котором они встречаются в регулярном выражении, начиная с 1. Например, пусть у нас есть следующее регулярное выражение: ^aa(bb)cc(dd)$. Заметим, что в этом случае у нас есть 2 группы. Они пронумерованы следующим образом:

Это значит, что в дальнейшем мы можем ссылаться на соответствующие им символы при помощи обратных ссылок. Если мы хотим сослаться на то, что соответствует (bb), то используем \1 (используется 1, потому что мы ссылаемся на группу 1). Чтобы сослаться на символы, соответствующие (dd), мы используем \2. Соединив это вместе, мы получим регулярное выражение ^aa(bb)cc(dd)\1$, соответствующее строке aabbccddbb. Обратите внимание, что мы использовали \1, чтобы сослаться на последние символы bb. \1 ссылается на то, что соответствовало группе (bb), то есть в данном случае на строку bb.

Также обратите внимание, что я выделил соответствовало. Я действительно имел в виду символы, которые соответствовали, а не те, которые могут соответствовать. То есть регулярное выражение ^aa(.+)cc(dd)\1$ соответствует строке aaHELLOccddHELLO, но не соответствует строке aaHELLOccddGOODBYE, потому что оно не может найти, что соответствовало группе 1 (в этом случае это последовательность символов HELLO) после последовательности символов dd (там оно находит GOODBYE).

Жадные и нежадные квантификаторы

Как вы помните, в представленной выше шпаргалке я говорил, что ? можно использовать, чтобы сделать предшествующий квантификатор нежадным. Но что же это значит? + — это жадный квантификатор, то есть он пытается повторить предшествующий токен как можно больше раз, а значит, попытается потребить как можно больше входных данных. То же самое относится и к квантификатору *.

Допустим, у нас есть строка <p>The Documentary</p> (2005) и регулярное выражение <.+>. Можно подумать, что оно будет соответствовать <p>, но это не так. На самом деле, соответствующей строкой будет <p>The Documentary</p>. Почему? Это связано со сказанным выше: + пытается потребить максимальное количество входных данных, то есть он остановится не на первом >, а на последнем.

Как же нам сделать квантификатор нежадным? Ну, возможно, вы уже устали это слышать (потому что я говорил об этом дважды), но чтобы сделать жадный квантификатор нежадным, после него нужно поставить вопросительный знак (?). Вот так, всё очень просто. Если вы сбиты с толку, не волнуйтесь, давайте рассмотрим пример.

Допустим, у нас есть та же строка: <p>The Documentary</p> (2005), но на этот раз мы хотим найти соответствие только между первыми < и >. Как это сделать? Достаточно добавить ? после +. Так мы получим регулярное выражение <.+?>. «Хм, ну ладно...», — можете подумать вы. «Но что же оно делает?». Оно делает квантификатор + нежадным. То есть это заставит квантификатор потреблять минимально возможный объём входных данных. В нашем случае «минимально возможный объём» — это <p>, то есть как раз то, что нам нужно! Если точнее, он будет соответствовать обоим p: <p> и </p>, но мы можем легко получить нужное нам, запросив первое соответствие (<p>).

Небольшое примечание о ^ и $

Если уж мы этого коснулись, я вкратце объясню, что же делают ^ и $. Как вы помните, ^ соответствует позиции непосредственно перед первым символом, а $ соответствует позиции сразу после последнего символа строки. Можно заметить, что в обоих регулярных выражениях выше (<.+> и <.+?>) мы их не использовали. Что это значит? Это означает, что соответствие не обязано начинаться в начале строки и заканчиваться в её конце. Взяв второе (нежадное) regex (<.+?>) и строку The Game - <p>The Documentary</p> (2005), мы получим наши ожидаемые соответствия (<p> и </p>), потому что не требуем, чтобы они начинались с начала и завершались в конце строки.

2. Регулярное выражение, определяющее простоту числа

Отлично, мы наконец закончили с теоретическим введением и теперь, поскольку уже знаем всё необходимое, можно погрузится в анализ того, как регулярное выражение ^.?$|^(..+?)\1+$ может соответствовать непростым числам (в их унарном виде).

Можно игнорировать ? в регулярном выражении, он нужен только для производительности (объяснения представлены ниже), потому что + делает нежадным. Если это сбивает вас с толку, просто игнорируйте его и представьте, что regex на самом деле имеет вид ^.?$|^(..+)\1+$ — оно работает так же, только медленнее (с некоторыми исключениями, например, когда число действительно простое и ? не обеспечивает никакой разницы). Объяснив, как работает это регулярное выражение, я также расскажу, что здесь делает ?; вы без проблем поймёте это, разобравшись во внутренней работе этого regex.

Во всех приведённых ниже рассуждениях предполагается, что число представлено в унарном виде (или по основанию 1). На самом деле, оно не обязано быть представленным в виде последовательности 1, это может быть любая последовательность, соответствующая .. Это значит, что 5 не обязано быть представленным как 11111, оно может быть представлено как fffff или BBBBB. Пока есть пять символов, всё будет работать нормально. Стоит отметить, что символы должны быть одинаковыми, смешение символов не допускается, то есть мы не можем представить 5 как ffffB, потому что получится смешение двух разных символов.

Высокоуровневый обзор

Давайте начнём с высокоуровневого обзора, а потом перейдём к подробностям. Наше регулярное выражение ^.?$|^(..+?)\1+$ состоит из двух частей: ^.?$ и ^(..+?)\1+$.

Предупрежу, что я немного обману вас в абзаце с объяснением регулярного выражения ^(..+?)\1+$. Ложь заключается в порядке, в котором движок regex проверяет кратные: на самом деле он начинает с наибольшего числа и движется к наименьшему, а не как я объясню ниже. Но можно игнорировать эту разницу, поскольку регулярное выражение всё равно соответствует тому же, но выполняет больше шагов (то есть на самом буду объяснять, как работает ^.?$|^(..+?)\1+?$: обратите внимание на дополнительный ? после +.

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

Движок regex сначала попытается найти соответствие ^.?$, затем, если это не удастся сделать, он попытается найти соответствие ^(..+?)\1+$. Стоит отметить, что количество совпавших символов соответствует совпавшему числу, то есть если совпало 3 символа, то получено соответствие числу 3, а если совпали 26 символов, то получено соответствие числу 26.

^.?$ соответствует строкам с нулём или одним символом (это соответствует числам 0 и 1).

^(..+?)\1+$ сначала пытается сопоставить 2 символа (соответствующие числу 2), затем 4 символа (соответствующие числу 4), затем 6 символов, затем 8 символов и так далее. По сути, оно пытается найти числа, кратные 2. Если это ему не удаётся, то оно пытается сопоставить первые 3 символа (соответствующих числу 3), затем 6 символов (соответствующих числу 6), затем 9 символов, затем 12 символов и так далее. Это значит, что оно пытается найти числа, кратные 3. Если ему не удастся это сделать, то оно продолжит искать числа, кратные 4, если и это не удастся, то числа, кратные 5 и так далее, пока число не будет равно длине строки (состояние неудачи) или не найдётся соответствие (состояние успеха).

Углубляемся

Обратим внимание, что обе части регулярного выражения начинаются с символа ^ и заканчиваются символом $, что заставляет находящееся между этими символами (.? в первом случае и (..+)\1+ во втором) начинаться с начала строки и заканчиваться в конце строки. В нашем случае строка — это унарное представление числа. Части выражения разделены оператором чередования, то есть соответствовать будет только одно из них или ни одно. Если число простое, то соответствия не будет. Если число непростое, то соответствие будет. Подведём итог:

• соответствовать будет или ^.?$, или ^(..+?)\1+$

• соответствие должно существовать для всей строки, то есть начинаться с начала и завершаться в конце строки

Но какие соответствия ищет каждая из этих частей? Надо запомнить, что если соответствие найдено, то число не является простым.

Как работает регулярное выражение ^.?$

^.?$ находит соответствие 0 или 1 символов. Это соответствие будет успешным, если:

• строка содержит только 1 символ, то есть мы имеем дело с числом 1, а оно по определению непростое.

• строка содержит 0 символов, то есть мы имеем дело с числом 0, а 0 определённо не является простым, потому что мы можем поделить 0 на что угодно, кроме самого 0, разумеется.

Если мы передадим строку 1, то ^.?$ найдёт соответствие, ведь в строке есть только один символ (1). Соответствие также произойдёт, если мы передадим пустую строку, поскольку, как мы объясняли выше, ^.?$ соответствует или пустой строке (0 символов) или строке из 1 символа.

Отлично, мы действительно хотим, чтобы наше regex считало 0 и 1 непростыми числами. Но этого недостаточно, поскольку существуют непростые числа кроме 0 и 1. И здесь нам на помощь приходит вторая часть регулярного выражения.

Как работает регулярное выражение ^(..+?)\1+$

^(..+?)\1+$ сначала попробует найти соответствия числам, кратным 2, затем кратным 3, затем кратным 4, затем кратным 5, затем кратным 6 и так далее, пока число, кратное которому оно хочет найти, не станет соответствовать длине строки или пока не найдётся успешное соответствие.

Но как это работает на самом деле? Давайте проанализируем!

Для начала сосредоточимся на скобках: здесь у нас есть (..+?) (помните, что ? просто делает это выражение нежадным). Обратите внимание, что здесь у нас есть +, то есть «один или больше предшествующий токен». Это regex сначала пытается сопоставить (..) (2 символа), затем (...) (3 символа), затем (....) (4 символа) и так далее, пока не будет достигнута длина строки или не найдётся успешное соответствие.

После сопоставления с каким-то количеством символов (давайте назовём это число x) регулярное выражение попробует посмотреть, является ли длина строки кратной x. Как она это делает? Существуют обратные ссылки. Это переносит нас ко второй части: \1+. Теперь, как объяснялось выше, она попробует повторить соответствие в группе 1 один или несколько раз (в этом и заключалась ложь, на самом деле, она скорее будет пробовать несколько или один раз) Это значит, что сначала она попытается сопоставить x * 2 символов в строке, затем x * 3, затем x * 4 и так далее. Если одно из этих сопоставлений окажется успешным, то выражение вернёт его (и это будет значить, что число непростое). Если сделать это не удастся (не получится это сделать, когда x * <число> превзойдёт длину строки, сопоставление с которой мы выполняем), оно попробует сделать то же самое, но с x+1 символами, то есть сначала с (x+1) * 2, затем (x+1) * 3, затем (x+1) * 4 и так далее (потому что теперь обратная ссылка \1+ ссылается на x+1 символов). Если количество сопоставляемых (..+?) символов достигнет длины строки, то процесс сопоставления regex прекратится и вернёт неудачу. Если найдётся удачное совпадение, то выражение вернёт его.

Время для примеров

Теперь я набросаю несколько примеров, чтобы вы точно всё поняли. Я покажу один пример, в котором регулярное выражение успешно находит соответствие, и другой, в котором ему это сделать не удаётся. Повторюсь, я немного обманываю вас о порядке подэтапов (вложенных, то есть тех, которые содержат ., например, 2.1, 3.2 и так далее).

В качестве примера успешного нахождения соответствия рассмотрим строку 111111. Длина сопоставляемой строки равна 6. Конечно, 6 — это непростое число, поэтому мы ожидаем, что regex успешно выполнит сопоставление. Давайте посмотрим, как это будет работать:

1. Сначала оно попробует найти соответствие ^.?$. Безуспешно. Часть слева от | возвращает неудачу 2. Пробуем сопоставить ^(..+?)\1+$ (часть справа от |). Она начинается с (..+?), то есть сопоставляет 11:

• 2.1 Обратная ссылка \1+ попытается сопоставить 11 дважды (то есть 1111). Безуспешно.

• 2.2 Обратная ссылка \1+ попытается сопоставить 11 трижды (то есть 111111). Успешно! Часть справа от | возвращает успех

Ого, как быстро! Так как часть справа от | была сопоставлена успешно, нашему регулярному выражению удалось успешно найти соответствие, а значит, число непростое.

В качестве примера неудачного сопоставления рассмотрим строку 11111. Длина сопоставляемой строки равна 5. Число 5 простое, поэтому мы ожидаем, что regex не сможет ни с чем выполнить сопоставление. Давайте посмотрим, как это работает:

1. Оно попытается сопоставить ^.?$. Неудачно. Часть слева от | вернёт неудачу 2. Оно попробует сопоставить ^(..+?)\1+$ (часть справа от |). Выражение начнёт с (..+?), то есть сопоставит 11:

• 2.1 Обратная ссылка \1+ попытается сопоставить 11 дважды (то есть 1111). Безуспешно.

• 2.2 Обратная ссылка \1+ попытается сопоставить 11 трижды (то есть 111111). Безуспешно. Мы превзошли длину строки (6 > 5). Обратная ссылка вернёт неудачу.

3. Теперь (..+?) выполнит сопоставление с 111:

• 3.1 Обратная ссылка \1+ попытается сопоставить 111 дважды (то есть 111111). Безуспешно. Мы превзошли длину строки (6 > 5). Обратная ссылка вернёт неудачу.

4. Теперь (..+?) выполняет сопоставление с 1111:

• 4.1 Обратная ссылка \1+ попытается сопоставить 1111 дважды (то есть 11111111). Безуспешно. Мы превзошли длину строки (8 > 5). Обратная ссылка вернёт неудачу.

5. Теперь (..+?) сопоставляет 11111:

• 5.1 Обратная ссылка \1+ попытается сопоставить 11111 дважды (то есть 1111111111). Безуспешно. Мы превзошли длину строки (10 > 5). Обратная ссылка вернёт неудачу.

5. (..+?) попытается сопоставить 1111111. Безуспешно. Мы превзошли длину строки (6 > 5). (..+?) вернёт неудачу. Часть справа от | вернёт неудачу

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

А теперь разберём символ ?

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

Как говорилось выше, ? делает предшествующий + нежадным. Что это значит на практике? Допустим, мы возьмём строку 111111111111111 (соответствует числу 15). Обозначим длину строки L. В нашем случае L=15.

При наличии ? специальный символ + попытается сопоставить предшествующий токен (в данном случае .) минимально возможное количество раз. Это значит, что первое (..+?) попытается сопоставить .., затем ..., затем ...., а затем ....., после чего всё (^.?$|^(..+?)\1+$) завершится успехом. То есть сначала мы будем тестировать делимость на 2, затем на 3, затем на 4 и затем на 5, после чего найдём соответствие. Можно заметить, что количество шагов в (..+?) было равно 4 (сначала оно сопоставляет 2, затем 3, затем 4 и затем 5).

Если бы мы убрали ?, то есть если бы у нас было (..+), то действия выполнялись бы в обратную сторону: сначала выражение бы попробовало сопоставить ............... (число 15, то есть наше L), затем .............. (число 14, то есть L-1) и так далее до ....., после чего regex в целом завершилось бы успехом. Стоит отметить, что хотя результат был бы таким же, как и в (..+?), в (..+) шагов было 11, а не 4. По определению, любой делитель должен быть не больше L/2, то есть 8 шагов были абсолютно ненужными вычислениями, потому что сначала мы проверили делимость на 15, затем на 14, затем на 13 и так далее до 5 (можно надеяться на соответствие только от числа 7 и ниже, потому что L/2 = 15/2 = 7.5, и первое целое число меньше 7.5 — это 7).

Шокирующая ложь

Как говорилось выше, на самом деле я вам соврал в объяснении того, как сопоставляются кратные величины числа. Допустим, у нас есть строка 111111111111111 (число 15).

Выше я давал такое объяснение: регулярное выражение начинает тестировать на делимость на 2. Оно делает это, сначала пытаясь сопоставить 2*2 символов, затем 2*3, затем 2*4, затем 2*5, затем 2*6, затем 2*7, после чего не сможет сопоставить 2*8, поэтому попытается протестировать делимость на 3, сначала выполняя сопоставление для 3*2 символов, затем для 3*3 символов, затем для 3*4 и затем для 3*5, где и добьётся успеха. На самом деле, так произошло бы, если бы регулярное выражение имело вид ^.?$|^(..+?)\1+?$ (обратите внимание на ? в конце), то есть если следующий за обратной ссылкой + будет нежадным.

Но на самом деле происходит наоборот. Выражение всё равно попробует сначала проверить делимость на 2, но вместо того, чтобы пытаться найти соответствие для 2*2 символов, оно начнёт с попытки найти соответствие для 2*7, затем для 2*6, затем для 2*5, затем для 2*4, затем для 2*3 и затем для 2*2, после чего потерпит неудачу и снова попробует удачу с делимостью на 3, сначала попробовав сопоставить 3*5 символов, и сразу добьётся успеха.

Обратите внимание, что во втором случае, который и происходит в реальности, требуется меньше шагов: 11 в первом случае и 7 во втором (в реальности оба случая потребуют больше шагов, чем представлено здесь; цель моего объяснения не в том, чтобы подсчитать их все, а чтобы показать смысл происходящего в обоих случаях; это просто набросок происходящего внутри движка). Хотя обе версии эквивалентны, объясняемая в посте более эффективна.

3. Случай Java

Вот код на Java, с которого всё началось:

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

Как вы помните, я говорил, что из-за тонкостей работы String.matches в Java регулярное выражение, соответствующее непростым числам, будет не тем, которое показано в примере выше (.?|(..+?)\1+), а на самом деле примет вид ^.?$|^(..+?)\1+$. Почему? Как оказалось, String.matches() сопоставляет строку целиком, а не любую подстроку строки. По сути, он «автоматически вставляет» все присутствующие в regex ^ и $, которые я объяснял в посте.

Если вам нужен способ не выполнять принудительное сопоставление всей строки в Java, можно использовать Pattern, Matcher и метод Matcher.find().

Всё остальное довольно понятно: если сопоставление выполнено успешно, то число непростое. В случае успешного соответствия String.matches() возвращает true (число непростое), в противном случае возвращает false (число простое), то есть мы получаем нужную нам функциональность, обращая то, что возвращает метод.

new String(new char[n]) возвращает String длиной n нулевых символов (. в нашем регулярном выражении находит с ними соответствие).

4. Примеры кода

Теперь, как я и обещал, настало время примеров кода!

Java

Хоть я уже дважды показывал этот пример в посте, для порядка приведу его снова.

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

Python

Я уже выражал свою любовь к Python, поэтому, разумеется, обязан привести пример на нём.

def is_prime(n):
    return not re.match(r'^.?$|^(..+?)\1+$', '1'*n)

JavaScript

Здесь я представлю две версии, одна работает в ES6, другая в предыдущих версиях.

Сначала версия для ECMAScript 6:

function isPrime(n) {
    var re = /^.?$|^(..+?)\1+$/;
    return !re.test('1'.repeat(n));
}

Особенность, доступная только в ECMAScript 6 — это метод String.prototype.repeat().

Если вы будете работать с предыдущими версиями ES, то всегда можете использовать Array.prototype.join(). Однако стоит отметить, что мы передаём n+1 методу join(), потому что на самом деле он помещает эти символы между элементами массива. То есть если у нас есть, например, 10 элементов массива, то «промежутков» только 9. Вот версия кода, которая будет работать в версиях до ECMAScript 6:

function isPrime(n) {
    var re = /^.?$|^(..+?)\1+$/;
    return !re.test(Array(n+1).join('1'));
}

Perl

И, наконец, время Perl. Я включил его, потому что регулярное выражение, которое мы исследовали в этом посте, было популяризировано Perl. Я говорю об однострочнике perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' <число> (<число> нужно заменить настоящим числом).

Кроме того, я раньше не работал с Perl, поэтому это стало подходящей возможностью попробовать. Итак:

sub is_prime {
    return !((1x$_[0]) =~ /^.?$|^(..+?)\1+$/);
}

Поскольку Perl сегодня — не самый популярный язык, возможно, вы незнакомы с его синтаксисом. Я разбирался с ним примерно 15 минут, так что уже стал экспертом, поэтому возьму на себя смелость объяснить синтаксис:

• sub — определяет новую подпрограмму (функцию)

• $_[0] — мы получаем доступ к первому параметру, переданному в нашу подпрограмму

• 1x<количество> — здесь мы используем оператор повторения x, который, по сути повторяет число 1 <количество> раз и возвращает результат как строку. Это схоже с тем, что '1'*<число> сделает в Python или '1'.repeat(<число>) в JavaScript.

• =~ — это оператор тестирования соответствия, он возвращает true, если регулярное выражение (его правая часть) имеет соответствие для строки (его левой части).

• !— оператор логического отрицания.

Я добавил это краткое объяснение, потому что сам не люблю оставаться в неведении относительно значения кода, а само объяснение всё равно заняло не так много места.

Заключение

Вот и всё! Надеюсь, теперь для вас не представляет загадки, как регулярное выражение может проверять число на простоту. Помните, что это далеко не самый эффективный способ, для этой задачи есть гораздо более эффективные алгоритмы, однако он забавный и интересный.

Я рекомендую сходить на сайты наподобие regex101 и разобраться самостоятельно, особенно если вы ещё не полностью понимаете, как работает объяснённое в посте. Одна из замечательных особенностей этого веб-сайта заключается в том, что там есть объяснение регулярного выражения (столбец справа), а также количество шагов, которое нужно будет сделать движку regex (прямоугольник прямо над полем модификаторов) — это хороший способ посмотреть на различия в производительности (по количеству сделанных шагов) в случаях жадных и нежадных операторов.