这个正则表达式如何找到素数？

Question

可能重复:
如何确定一个数字是否是正则表达式的素数？

此页面声称此正则表达式发现非素数(并通过反例:素数):

/^1?$|^(11+?)\1+$/

这怎么找到素数？

Answer 1

我认为这篇文章解释得很好,但我也会尝试一下.

输入是一元形式.1是1,2是11,3是111等.零是空字符串.

正则表达式的第一部分将0和1匹配为非素数.第二个是魔术踢的地方.

(11+?)从找到除数开始.它首先被定义为11,或者2. \1是一个引用先前捕获的匹配的变量,因此\1+确定该数字是否可被该除数整除.(111111首先将变量赋值给11,然后确定剩余1111的11重复,所以6可以被2整除.)

如果该数字不能被2整除,则正则表达式引擎会递增除数.(11+?)变成了111,我们再试一次.如果在任何时候正则表达式匹配,这个数字有没有产生剩余的约数,所以数量不能是素数.

Answer 2

我花了一分钟才意识到这是针对base-1中的数字(一元？)

这个ycombinator讨论中的几个人很好地解释了这一点.实际上这些解释比我想的更简洁,所以我会把它留给链接.