^.?$|^(..+?)\1+$ 为啥能召唤质数？

Description

翻译&时轴：贰鼠
额外翻译、审核、时轴、后期处理：Origami Alice

本视频“How on Earth does ^.?$|^(..+?)\1+$ produce primes?” （https://www.youtube.com/watch?v=5vbk0TwkokM）
于2024年10月30日上传至油管
-----------------------------------------------------
^.?$|^(..+?)\1+$

<道具已售完>

Illya Gerasymchuk 的精彩博文：“揭秘检查数字是否为素数的正则表达式”：https://illya.sh/the-codeumentary-blog/regular-expression-check-if-number-is-prime/

感谢所有分享此正则表达式历史记录的人。它似乎是 25 年前由一位名叫 Abigail 的 Perl 程序员编写的。

向观众 Dave Cross 致敬，他在 2000 年的一篇博客文章中发现了这一已知最早的提及：http://test.neilk.net/blog/2000/06/01/abigails-regex-to-test-for-prime-numbers/

感谢观众 Chris Lawrence 和 Jimmy Diep 提出这个主题。

特别感谢我的 Patreon 支持者。他们为我提供了所有质数。https://www.patreon.com/standupmaths

更正：（已在B站上修改）
- 有几个人纠正我，说正则表达式是零索引的，只是 \0 指的是整个匹配的字符串。
- Mike Salisbury 等人指出，重复通配符表的最左列不应该被包含进去。否则字符串的长度可能会匹配单个素数的长度。
- 在6:07，我把“以m开头和结尾”写成了“以m开头和结尾”，而我的意思是以“s”结尾。没有人比 Timur Sultanov 更积极地纠正这个错误的观众了。
- 有些人担心我对"rejex"的发音。
- 如果还有发现错误，请联系

摄影、特效、以及编辑来自于 Alex Genn-Bash
写作和表演者是 Matt Parker
Sam Hartburn 提供了额外的材料
乱扔数字是 Lucie Green 干的事
诡异的灯光等出品员是 Nicole Jacobus
音乐来源于 Howard Carter
设计来自 Simon Wright 和 Adam Robinson

马特·帕克：讲脱口秀的数学家
网页: http://standupmaths.com/

Comments

OnyxAmber 2025-04-26

当我想对正则表达式破口大骂的时候，正则表达式精准匹配并屏蔽掉了我的脏话

♥ 1435 ↩ 8

響 2025-04-26

我有一个问题，我打算用正则表达式解决它。很好，现在我有两个问题了。

♥ 851 ↩ 16

苦莫kvmeo 2025-04-26

我一直不知道那些异世界的平民，看见一个人叽里咕噜一大堆，最后变出了个大火球是个什么心情。 …… 现在我知道了……

♥ 470 ↩ 5

Sunchy321 2025-04-26

[笑哭]什么正则表达式入门。。话说回来这个效率应该跟暴力搜索差不多

♥ 377 ↩ 10

四方霸主 2025-04-26

省流：九九乘法表不要第一列（一几得几）后，判断这个数字在不在剩下的结果里，在就是合数，不在就是质数。（别较真问我81之后的数字，问就是你自己去扩写九九乘法表成不可思议不可思议乘法表）[doge]

♥ 243 ↩ 11

icai 2025-04-26

(($:@(<#]),=#,~$:@(>#])){~?@#)^:1<# 这行能实现排序

♥ 447 ↩ 15

不是鲈鱼 2025-04-26

[doge]都归功于后引（back reference），加上它以后正则表达式的表达力已经超过正则语言了，甚至上下文无关文法都没办法匹配长度为质数的字符串（泵引理可证）。之前有篇论文证了不限数量的后引的正则表达式的匹配问题是 NP 完全。

♥ 170 ↩ 7

野人学派 2025-05-01

省流：一、输入一个自然数n；二、生成length为n、字符全为"1"（别的字符也行）的字符串；三、匹配正则表达式： 1、竖线|表示或； 2、竖线左边^.?$匹配length为0或1的字符，若匹配到返回true，即n为0或1； 3、竖线右边^(..+?)\1+$ a、先找到字符串开头2个字符，用这2个字符往后比对，在之后要找到一组以上的对应，一直找到字符串末尾刚好没有剩余字符，即为匹配，返回true——即两个两个数，数出两组以上，最后刚好数完，即n为2的2以上倍数； b、若不然，再找到字符串开头3个字符，用这3个字符往后比对，…没有剩余字符，即为匹配，返回true…即n为3的2以上倍数； c、若不然，再找到字符串开头4个字符，用这4个字符往后比对，…没有剩余字符，即为匹配，返回true…即n为4的2以上倍数； ⋮ n、若不然，再找到字符串开头n个字符，刚好取到字符串末尾，其后不可能再找到一组字符与其对应，表达式匹配过程终止，未找到匹配，返回false——即确定n不是2、3、4、…、n的2以上倍数；四、取反，则质数返回true，非质数返回false。评价：算法效率极低，但也是一种可行的方法。

♥ 132 ↩ 4