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

Приветствую всех, и сегодня поговорим о прекрасном. Как написать программу из одной строки, выводящую простые числа?

Простое число - это натуральное число больше единицы (2, 3, 4, и так далее), которое делится только на себя и на единицу. 3, 5, 7, 11, 13, 17 - простые числа. Их бесконечно много и с ними связано много интересных фактов (о которых как-нибудь в другой раз).

Однострочник может иметь такой вид:

perl -E 'while(++$n){say $n if (1x$n)!~/^(1|(11+)\2+)$/}'

Давайте же разберем эту программу!

Ключ -E означает, что Перл трактует остаток команды как код программы и выполняет его. Он нужен для однострочников - чрезвычайно удобного и мощного инструменте в умелых руках. Есть еще ключ -e - отличия в том, что -E подключает новые возможности, например функцию say.

У нас текст программы - в одинарных кавычках. Он состоит из вечного цикла, в котором переменная $n увеличивается, начиная с 1. Тело цикла имеет вид

say $n if (1x$n)!~/^(1|(11+)\2+)$/

Здесь переменная $n выводится на стандартный вывод функцией say (она добавляет конец строки к тому, что выводит), если выполнено условие оператора if. Оно имеет вид

(1x$n)!~/^(1|(11+)\2+)$/

Оператор !~ сравнивает строку слева с регулярным выражением справа, и возвращает истину, если совпадения нет. Это отрицание оператора =~ который истинен, если совпадение есть. Строка слева строится с помощью "умножения" x - этот оператор повторяет строку слева столько раз, сколько указано справа. В нашем случае получается строка из $n единичек - единичный код числа. Например, 5 запишется как 11111, а 3 - как 111.

Регулярное выражение заключено в косые черты: //. Это, кстати, не обязательно, и можно написать m|...| или m{...} - на Ваш тонкий вкус. Оператор m позволяет использовать любые скобки (даже символы точка, запятая и точка с запятой годятся, не считая пар (), [], {} и <>). Бывает полезно, если в выражении много символов /. Выражение у нас такое:

^(1|(11+)\2+)$

Символ ^ совпадает в начале текста, а символ $ - в конце. Таким образом, строка должна совпасть целиком. Совпасть с тем, что указано в скобках:

1|(11+)\2+

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

Первая альтернатива - это просто единица. Это необходимо, чтобы отсеять число один, которое не простое и не составное. Рассмотрим вторую:

(11+)\2+

Здесь должна найтись группа (она в скобках), состоящая из единицы и еще одной или более единиц (квантификатор "плюс" означает "один или более") - то есть, две или более единиц.

Это группа улавливается скобками, и скобки эти - вторые по счету в выражении (скобки считаются по порядку открывающей скобки). То, что ими уловлено, доступно в том же выражении как \2. И опять использован квантификатор "плюс".

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

Задания для размышления

• Что будет, если заменить \2 на такую же группу (11+)?
• Можно ли поставить ++ после $n?
• Как вывести все простые числа до 100, не задействуя переменную $n?
• Можно ли опустить скобки вокруг 1x$n?
• Что будет, если убрать альтернативу для единицы? Нужна ли первая пара скобок? Как ее убрать?
• Как Вам больше по душе: "if !~" или "unless =~" ?