[闲聊] 原来正规表示法可以用来找质数

楼主: art1 (人,原来不是人)   2022-09-26 01:49:22
http://vimcasts.org/episodes/vimgolf-prime-numbers/
这原本是 vimgolf 的题目,但解法很有意思,因此作者特别介绍,也找出最初的出处
首先要把每个数改用符号表示,像是 1 就用一个 *,2 就用 **,3 就用 ***
这连结的解法是用 Tab,最早出处是用 1
最主要的部份
(<Tab><Tab>+)\1+
最早出处则是 (11+?)\1+
目前的理解是括号内要找的是从二开始递增的数,\1 则是括号找到的数的倍数
有倍数肯定不是质数
两个解法差了一个 ?,我猜有加 ? 的效能应该比较好?
作者: OSDBNetwork (路人甲)   2022-09-26 16:36:00
+ 后面的 ? 应该是指 Lazy Quantifier
作者: LPH66 (-6.2598534e+18f)   2022-09-26 19:22:00
对, 这里的 Lazy 用来让因子从小的开始试11+? 会先配出 11 当做 \1 后试着配对 \1+如果成功那就是 2 的倍数, 不成功的话倒回会倒到 +? 这里然后延长一个试, 所以就会试 111 当做 \1 来配对 \1+在这里成功就是 3 的倍数, 依此类推基本上就是连结里的图从下面试上去那当数字有小因子时会比较快结束
作者: glo6e (ezdodance)   2022-12-25 22:52:00

Links booklink

Contact Us: admin [ a t ] ucptt.com