求解释用于质数判定的Python正则表达式^1?$|^(11+?)\1+$工作原理
正则实现质数识别的原理拆解
先澄清一个入门阶段容易出现的认知偏差:这段代码完全没有用到任何位运算符,你感知到的位运算联想是对匹配逻辑的错位理解,整个实现的核心是固定长度重复字符串匹配,和
&、|、^这类位操作没有任何关联。
核心设计巧思
这段代码没有直接对数字本身做因数判断,而是做了一层非常直观的转换:
- 把输入的整数
n,转换成由n个连续1组成的字符串,比如输入3就得到'111',输入4就得到'1111' - 正则的匹配目标不是直接识别质数,而是识别所有属于「非质数」的场景——只要正则能在这个全1字符串上匹配成功,对应的数字就不是质数;匹配失败,才是质数。
逐段拆解正则逻辑
整个待解析的正则表达式为^1?$|^(11+?)\1+$,其中竖线|是正则的「或」逻辑,代表两个分支只要满足任意一个,就算匹配成功,分别对应所有非质数的两类场景:
第一个分支:^1?$
这个分支专门匹配最小的两类非质数:
^代表字符串开头,$代表字符串结尾1?代表匹配0个或者1个连续的1
也就是说,只要全1字符串的长度是0或者1(对应数字0、1),就会被这个分支直接匹配,这两个数本来就不属于质数范畴,完全符合判定逻辑。
第二个分支:^(11+?)\1+$
这个分支是识别所有大于1的非质数(也就是合数)的核心,逐段拆解:
(11+?):第一个捕获组,匹配至少2个连续的1——也就是这个组匹配到的片段长度一定≥2,比如11、111、1111都属于可被捕获的片段,末尾的+?是非贪婪匹配,作用是尽可能匹配更短的片段以提升效率,不影响最终判定结果。\1+:正则的反向引用语法,意思是「把刚才捕获组匹配到的固定片段,原封不动重复1次、2次、3次……只要重复后的长度刚好等于整个全1字符串的长度,就算匹配成功」
举几个实际的匹配例子就很容易理解:
- 数字4对应的全1串是
1111:捕获组可以先匹配长度为2的片段11,反向引用要求把11再重复1次,刚好拼出完整的4个1,匹配成功,判定4为非质数。 - 数字6对应的全1串是
111111:不管捕获组选长度2的11(重复3次)还是长度3的111(重复2次),都能拼出完整字符串,匹配成功,判定6为非质数。 - 数字3对应的全1串是
111:捕获组要求匹配至少2个1,最短能选的片段是长度2的11,剩下1个1根本没法拼成完整的重复片段,没有任何办法用「长度≥2的固定片段重复若干次」拼出整个字符串,正则匹配失败,判定3为质数。
这个逻辑刚好和合数的数学定义完全对应:所有大于1的非质数,都可以拆成两个≥2的整数相乘,也就是能表示为「长度为a的1,重复b次,总长度a*b=n」;反过来,所有质数都不存在这样的拆分方式,自然无法被正则匹配到。
代码的逻辑闭环
再回头看核心的判断函数:
def is_prime(n): return re.match(r'^1?$|^(11+?)\1+$', '1' * n) is None
函数返回的是「正则匹配结果是否为空」——只要没匹配上所有非质数的判定规则,就返回True,代表对应数字是质数,整个逻辑是完全自洽的。
参考代码中后续循环、累计质数列表的逻辑,只是为了演示完整运行效果写的配套取数流程,和核心的正则判定原理没有关联。
注意:这套实现只是用来演示正则能力的趣味Demo,实际使用时性能极差——数字越大,生成的全1字符串越长,正则引擎需要做大量回溯运算,完全不适合生产场景的质数判断
内容的提问来源于stack exchange,提问作者TrueDarkRonin
相关产品推荐
相关产品推荐

