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

Question

От this article,

/^1?$|^(11+?)\1+$/ проверяет, является ли число (его значение в унальном) простым или нет.

Используя это, perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;' возвращает список простых чисел.

У меня недостаточно опыта работы с Perl, но я понимаю, что регулярное выражение будет true для числа, которое не является простым. Итак, если мы напечатаем все числа, которые не производят true с этим выражением, у нас есть список простых чисел. То, что пытается выполнить запрос perl.

О регулярных выражений часть,

^1?$ часть для подсчета 1, как не первична

^(11+?)\1+$ для согласования не простых чисел, начиная с 4

---

То, что я не понять, почему ? в регулярном выражении необходимо вообще. По мне /^1$|^(11+)\1+$/ должно быть прекрасно, и на самом деле

perl -l -e '(1 x $_) !~ /^1$|^(11+)\1+$/ && print while ++$_;' дает мне тот же набор простых чисел.

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

Не соответствует ли ? нулю или одному вхождению предшествующего ему выражения?

Answer 1

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

Второй ? предназначен только для эффективности. + обычно «жадный», что означает, что он соответствует количеству символов, которые доступны, а затем возвращается, если остальная часть регулярного выражения не соответствует. +? делает его неживым, поэтому он соответствует только 1 символу, а затем пытается сопоставить больше, если остальная часть регулярного выражения не соответствует. (См. the Quantifiers section of perlre для получения более подробной информации о жадных и нежелательных соответствиях.)

В данном регулярном выражении, то (11+?) означает, что он проверяет делимость на 2 ('11'), а затем 3 ('111'), затем 4 и т.д. Если вы использовали (11+), было бы проверить делимость на N (само число), затем N-1, затем N-2 и т. д. Так как делитель должен быть не больше N/2, без ?, он будет тратить время на тестирование множества «потенциальных» делителей, которые не могут работать. Это все равно будет соответствовать нечетным числам, только медленнее. (Кроме того, $1 был бы самым большим делителем вместо самого маленького.)

Answer 2

Первый ? сделает «» (пустая строка, унарный ноль) не будет простым числом. Ноль определяется как нечётный.

Второе - другое; он останавливает регулярное выражение от жадного соответствия. Это должно значительно улучшить производительность матча, так как первая часть этого раздела ((11+)) не будет потреблять почти всю строку, прежде чем придется отступать. Если вы опускаете вопросительный знак, вы эффективно проверяете, является ли нечетным n делимым на n-1 и поэтому один вниз; если вы включите его, вы тестируете делимость на два первых и так далее. Очевидно, что цифры, как правило, делятся на более мелкие факторы чаще, поэтому ваш матч будет быстрее.