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

Question

С этой статьи ,

/^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 символу, а затем пытается сопоставить больше, если остальные регулярные выражения не совпадают.(См. раздел Quantifiers в perlre для получения дополнительной информации о сопоставлении жадность и сопоставление без жадности.)

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

Answer 2

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

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