Где-то во всех ваших прошлых поисках алгоритмов простых чисел вы могли встретить что-то вроде этого:

Что это? Это способ проверить, является ли число простым! И вам даже не нужно писать цикл for!

Довольно дико, правда?

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

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

Итак, что происходит?

Итак, в основном эта функция состоит из трех шагов:

  1. превратить число в унарную форму
  2. проверьте, это 0 или 1
  3. проверьте, не делится ли оно на любое число больше 1

Шаг 1

Итак, сначала мы собираемся превратить число, которое мы проверяем, в его унарную форму. «Унарный» - это, по сути, причудливый способ обозначения счетных отметок (т. Е. 3 становится «111», 4 становится «1111» и т. Д.).

Это достигается с помощью этого фрагмента кода:

По сути, это означает: «Создайте массив с n + 1 пустыми слотами и объедините все эти пустые значения с помощью единиц».

Я предпочитаю использовать метод String.prototype.repeat () из ES6, который выглядит так:

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

Большой! Двигаемся дальше!

Шаг 2

Итак, теперь мы собираемся начать проверять, соответствует ли эта унарная версия нашего числа регулярному выражению. Регулярное выражение можно разбить на две части: все слева от | (которое работает как оператор ИЛИ) и все справа от него.

Левая сторона будет:

Итак, давайте рассмотрим это по отдельности.

Во-первых, ^.

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

Далее у нас есть 1.

Здесь 1 просто говорит, что нужно найти в строке символ «1». Мы могли бы создать унарную строку из всех 2 (т.е. 3 становится «222» и т. Д.), И этот символ должен быть 2. Он просто должен быть таким же, как любой символ, который вы использовали для создания своей строки.

Далее идет ?.

Это означает, что предшествующий ему символ является необязательным, поэтому регулярное выражение будет соответствовать нулю «1» или одной «1» (то есть «» или «1»).

Последний символ - $.

Как я уже сказал, это аналог ^. Вот как мы знаем, что в конце нет остатка!

Итак, эта часть нашего регулярного выражения выполняет шаг 2, проверяя, было ли переданное число 0 или 1.

Большой! Следующий!

Шаг 3

Здесь начинается самое интересное. Теперь нам нужно посмотреть, кратно ли это число чему-либо большему, чем 1. Если да, то это не простое число! Итак, давайте посмотрим на правую часть нашего регулярного выражения:

Здесь у нас есть тот же шаблон ^...$, что и раньше, в котором говорится, что строка должна начинаться и заканчиваться в этих местах, чтобы совпадение сработало. Итак, сначала давайте посмотрим, что делают круглые скобки.

(11+?)

Скобки здесь создают группировку, что важно, потому что мы проверяем кратность. Если мы хотим увидеть, что наше число не кратно 2, нам нужно сгруппировать все «1» в «11» и выяснить, есть ли остаток.

Первые два 1 в круглых скобках такие же, как и предыдущие 1. Они просто сопоставляют «1» в унарной строковой версии числа.

+ говорит, что соответствует одному или нескольким предшествующим символам. Таким образом, для совпадения должно быть не менее двух «1», но любое количество «1» больше этого также будет соответствовать.

? после + очень важен. Это делает + «не жадным». Это означает, что сначала он будет соответствовать наименьшей возможной части строки. Он начнется с совпадения только двух «1», затем трех «1», затем четырех и так далее. Если бы ? отсутствовал, то + был бы жадным и соответствовал бы как можно большей части строки, что для нас является всей строкой, поскольку наша строка содержит только один символ.

Итак, теперь, когда у нас есть группировка из двух или более единиц «1», нам нужно проверить, будут ли кратные нашей группировки соответствовать остальной части строки без остатка (то есть до самого конца строки). Вот где это входит:

\1+?

Итак, первый бит - это \1, который называется обратной ссылкой. Он будет ссылаться на то, что первая группировка была в нашем регулярном выражении. Думайте об этом как о переменной регулярного выражения. Это относится к тому, что заключено в круглые скобки.

Знак +? после него должен показаться знакомым. Это не жадная проверка того, что может быть одна или несколько итераций нашей обратной ссылки.

Таким образом, если (11+?) соответствует строке «11», наша обратная ссылка также будет соответствовать «11», поэтому наше регулярное выражение ищет все, что кратно «11», начиная с «1111», затем «111111» и т. Д. Если это не удается (если наше число нечетное), то оно вернется и добавит еще одну «1» к биту в круглых скобках и попытается сопоставить все, что кратно «111».

Если наше регулярное выражение когда-либо возвращает истину для совпадения, это означает, что наше число равно 1) 0 или 1 или 2) кратному числу, большему 1. Это означает, что оно не является (т.е. !) простым числом! Круто, правда?

Взгляните на этот код еще раз, чтобы убедиться, что вы все понимаете:

И здесь вы можете увидеть версию с красивым синтаксисом ES6, который избавляет от необходимости создавать ненужный массив:

Это все, что у меня есть. Спасибо за прочтение! Надеюсь, вам понравилось, и вы чувствуете, что готовы творить магию регулярных выражений самостоятельно.

Изменить:

Несколько человек спрашивали меня об эффективности такой проверки простых чисел. Я должен был упомянуть с самого начала и извиниться за то, что это ОЧЕНЬ неэффективный способ проверить, является ли число простым.

Обычные методы определения того, является ли число простым, проверяют делители только до квадратного корня из числа, но здесь мы проверяем полностью до половины числа.

Само по себе регулярное выражение - это только часть проблемы. String.prototype.repeat () - это итерация, которая повторяется n раз, а для очень больших чисел это само по себе занимает много времени.

Регулярному выражению также мешает тот факт, что максимальная длина строк в большинстве браузеров составляет около 268 миллионов, поэтому вы не можете проверять простые числа больше этого (например, мое любимое простое число, 1000000000000066600000000000001).

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