这个正则表达式如何工作？

Question

从这篇文章来看,

/^1?$|^(11+?)\1+$/ 检查一个数字(它在一元中的值)是否为素数.

使用它,perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;'返回素数列表.

我没有足够的Perl经验,但据我所知,正则表达式对于非素数的数字都是正确的.因此,如果我们使用此表达式打印所有不产生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个字符,然后尝试,如果正则表达式的其余部分不匹配匹配更多.(有关贪婪与非贪婪匹配的更多信息,请参阅perlre的Quantifiers部分.)

在这个特定的正则表达式中,它(11+?)意味着它通过2('11'),然后3('111'),然后是4等(11+)来测试可分性.如果你使用它,它将用N(数字本身)测试可分性,然后是N-1,然后是N-2因为除数必须不大于N/2,否则?它会浪费时间测试很多不可能有效的"潜在"除数.它仍然会匹配非素数,只是更慢.(另外,$1将是最大的除数而不是最小的除数.)

Answer 2

第一个?将使""(空字符串,一元零)不是素数.零定义为非素数.

第二个是不同的; 它从贪婪匹配中停止正则表达式.它应该大大提高匹配的性能,因为该section((11+))的第一部分在不得不回溯之前不会消耗几乎整个字符串.如果你省略问号,你就可以有效地测试奇数n是否可被整除n-1,所以一个向下; 如果你包括它,你首先测试两个可分解性,依此类推.显然,数字往往可以被更小的因素整除,所以你的匹配会更快.