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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

爱意满满的作品展示区。

这是一个创建于 2733 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

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

质数

博文

blog

表达

10 条回复 • 2017-06-06 18:37:32 +08:00

Kilerd

2017-06-02 16:45:03 +08:00

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

geelaw

2017-06-02 16:52:10 +08:00 via iPhone

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

whileFalse

2017-06-02 16:59:55 +08:00

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

geelaw

2017-06-03 08:13:02 +08:00

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

LokiSharp

2017-06-05 12:56:46 +08:00

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

geelaw

2017-06-05 13:01:40 +08:00

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

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

msg7086

2017-06-06 07:19:10 +08:00

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

geelaw

2017-06-06 10:18:53 +08:00 via iPhone

@msg7086 右上角可以切换主题

leafin

2017-06-06 16:46:46 +08:00

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

geelaw

2017-06-06 18:37:32 +08:00

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