用正则表达式匹配质数/合数，以及为什么你不该这样做

爱意满满的作品展示区。

This topic created in 3443 days ago, the information mentioned may be changed or developed.

一个很古老的奇技淫巧是把一个数编码为一进制（用 n 个连写的 1 代表 n，例如用 11 代表 2，用 111111 代表 6 ），然后用正则表达式 ^1?$|^(11+)\1+$ 判断这个数是否不是质数。

然而这样做十分慢。我在一个人的 blog 下指出这个正则表达式判断是否不是质数是非常慢的，但是他说他的测试表明正则表达式 反而更快，这怎么可能呢？

答案在 blog 正文里面：链接到我的博文，链接到 jawil 的博文。

注：我的博文是在我对他的博文的评论中有感而发写出的，我的博文是英语的，他的博文是汉语的，大家可以自行选择。

质数

博文

blog

表达

10 replies • 2017-06-06 18:37:32 +08:00

Kilerd

Jun 2, 2017

你的博客需要重写鼠标上下滚动事件至左右滚动

geelaw

Jun 2, 2017 via iPhone

@Kilerd 我知道，但我不想写，因为这很麻烦……你可以尝试：用户 Shify+滚轮，有些浏览器可以这样横滚；或者把窗口变窄……

whileFalse

Jun 2, 2017

不说别的，判断 2^30 + 1 是否是质数就需要 1G 内存。

geelaw

Jun 3, 2017

更新了一下，讨论了一下 greediness

LokiSharp

Jun 5, 2017

你的博客。。。为什么一会写中文一会写英文。。。

geelaw

Jun 5, 2017

@LokiSharp 因为有些内容的受众不说汉语，对于我认为需要让不说汉语的人也能看的内容，我会选择用英语。有些内容（实际上只有一篇）具有多个（两个）语言的版本。

实际上，你可以发现这个 blog 各个语言的本地化做得比较细心~包括汉语和英语中引号是全形还是半形的问题，以及页脚链接的 href 是不同的。

msg7086

Jun 6, 2017

……是不是只有我一个人看到黑底白字的时候会眼睛疼？

geelaw

Jun 6, 2017 via iPhone

@msg7086 右上角可以切换主题

leafin

Jun 6, 2017

我只想说，1 进制里面是不包括 1 这个数字的，就好象二进制没有 2，8 进制没有 8

geelaw

Jun 6, 2017

@leafin 用 n 个 0 是一样的。另外你犯了望文生义的错误，“一进制”并不是“ N 进制”的一个特例：其他进位制都是幂进位制的，数字的长度是它值的对数级别；一进制的数字长度等于数字大小。