Как это регулярное выражение работает?
От этой статьи,
/^1?$|^(11+?)\1+$/ проверки, является ли число (его значение в унарном) простым или нет.
Используя это, perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;' возвращает список простых чисел.
У меня нет достаточного опыта с Perl, но что я понимаю, то, что регулярное выражение будет верно для числа, которое не является простым. Так, если мы печатаем все числа, которые не производят истинное с этим выражением, у нас есть список простых чисел. Это - то, что запрос жемчуга пытается сделать.
О regex части,
^1?$ часть для подсчета 1 как не главная
^(11+?)\1+$ для соответствия не простые числа, запускающиеся от 4.
То, что я не понимаю, - то, почему ? в regex, необходимом вообще. Согласно мне /^1$|^(11+)\1+$/ должен быть очень хорошо и на самом деле
perl -l -e '(1 x $_) !~ /^1$|^(11+)\1+$/ && print while ++$_;' дает мне тот же набор простых чисел.
Есть ли какой-либо дефект в моем понимании регулярного выражения? Почему ?s необходимый?
Не ? предполагаемый соответствовать нулю или одному возникновению выражения, предшествующего ему?
2 ответа
Первый ? предназначен для сопоставления пустой строки (т.е. 0) как нецелого числа. Если вам не важно, соответствует ли regexp 0, то это не обязательно.
Второй ? - только для эффективности. + обычно является "жадным", что означает, что он сопоставляет столько символов, сколько доступно, а затем отступает, если остальная часть регекспа не совпадает. +? делает его не жадным, то есть он подбирает только 1 символ, а затем пытается подобрать больше символов, если остальные символы не совпадают. (Подробнее о жадном и нежадном подборе см. в разделе Квантификаторы в perlre)
В данном конкретном выражении (11+?) означает, что проверяется делимость на 2 ('11'), затем на 3 ('111'), затем на 4 и т. д. Если использовать (11+), то проверяется делимость на N (само число), затем на N-1, затем на N-2 и т. д. Поскольку делитель должен быть не больше N/2, без ? он потратит время на проверку множества "потенциальных" делителей, которые не могут работать. Он по-прежнему будет находить не простые числа, просто медленнее. (Кроме того, $1 будет наибольшим делителем, а не наименьшим)
Первое ? сделает "" (пустая строка, унарный ноль) не простым числом. Ноль определяется как непростое.
Второй отличается; он предотвращает жадное сопоставление регулярного выражения. Это должно значительно улучшить производительность сопоставления, поскольку первая часть этого раздела ( (11 +) ) не займет почти всю строку, прежде чем придется выполнить возврат. Если вы опустите вопросительный знак, вы эффективно проверяете, делится ли нечетное n на n-1 и так на единицу меньше; если вы включите его, вы сначала проверяете делимость на два и так далее. Очевидно, что числа чаще делятся на меньшие множители, поэтому совпадение будет быстрее.