正则表达式判断质数-有点意思
2023-03-31 00:00:00 # 正则表达式 # 随笔

发现

最近偶然发现一篇文章说正则可以判断一个数是不是素数，当时就懵了，一看正则：

1
^1?$|^(11+?)\1+$

第一眼没看懂，这不都是判断1么，感觉和数字没关系，细看文章内容，他又说道用Ruby写了个代码

1
2
3
def is_prime(n)
  ("1" * n) !~ /^1?$|^(11+?)\1+$/
end

我让ChatGPT改造了一下：

1
2
3
4
5
6
def is_prime(n)
  ("1" * n) !~ /^1?$|^(11+?)\1+$/
end
print "请输入一个数字："
n = gets.chomp.to_i
puts "#{n} 是素数吗？#{is_prime(n)}"

这段代码作用是接收一个数字输入n，然后把n转成n个1组成的字符串，再用这段字符串去匹配正则，然后输出是不是素数。

由于我不会Ruby，所以找了个在线运行的网站试了一下Online Compiler - online editor，这个网站可以支持很多种语言在线编译运行。右上角选Ruby就可以体验。经过测试，确实返回的结果都是对的，这接下来就得研究一下这个正则了，为什么可以判断素数？

正则解析

1
^1?$|^(11+?)\1+$

这个正则可以分成两部分，因为中间有个 | ，就是或的意思，前半段正则和后半段只要有一段匹配到就可以。

  1. ^1?$ 这段比较简单，^匹配字符串开始，$匹配字符串结束，中间1就表示匹配一个1字符，?表示匹配0次或1次, 也就是说这段作用是匹配0个或1个’1’字符，代码里就是判断n==0或者n==1的情况
  2. ^(11+?)\1+$ 这段就有意思了，先看(11+?)，这是一个分组(子表达式)，11就是匹配11，+表示匹配1次或多次，?是非贪婪模式，所以这个分组将尽可能短地匹配字符串，作用是匹配以2个或以上的 1 开头的字符串，并将其捕获到分组 1 中。比如可以匹配11、111、1111、11111等等。
    \1+ 这个就是再次匹配分组1，然后+表示1次或多次。作用就是匹配分组 1 中的内容重复1次或多次。
    那么第二段结合起来就可以匹配到1111、111111111、111111，加粗的就是分组1的内容，后面就是分组1重复了多次，不知道能不能理解这个意思。

下面结合数字来看一下
正则匹配

  • 比如3 转换字符串 111，这个就匹配不到，因为没办法找到2个或以上的1 （分组1要求要2个或以上的1），然后有重复多次的
  • 比如n==9，111111111， 分组1就是3个111，重复3次，可以匹配到
  • n==25，分组1就是11111，重复5次，可以匹配到
  • n==49，分组1就是1111111，重复7次，可以匹配到
  • n==17，匹配不到，因为没办法找到2个或以上的1，然后重复多次
  • n==6，分组1是11 （因为懒惰模式，尽可能匹配短的字符串），重复3次

现在应该看出来了，这个正则匹配的就是2、3、5、7、11等等这些数的倍数，尝试找到n的因数，素数是没有除了1和他本身之外的因数，所以这个正则是对的。

有点意思

性能

我没有自己测试，而是直接问了ChatGPT

("1" * n) !~ /^1?$|^(11+?)\1+$/ 这段代码性能怎么样？

这段代码的性能与输入数字的大小有关，并且在某些情况下可能比传统的质数检测算法要快。
首先，该代码使用了字符串重复操作 "1" * n 来构造一个长度为 n 的字符串，然后将其传递给正则表达式进行匹配。因此，如果输入的数字很大，那么字符串重复操作可能会耗费较多的时间和内存。另外，如果输入的数字是质数，那么该正则表达式需要遍历整个字符串才能确定它是质数，这可能会导致性能瓶颈。
然而，在某些情况下，该代码的性能可能会优于传统的质数检测算法。例如，对于较小的数字（比如小于 10^6），该代码通常比试除法或米勒-拉宾素性检验等传统算法更快。这是因为正则表达式引擎通常在处理短字符串时具有很高的效率，并且可以充分利用现代计算机的并行处理能力。
总之，这段代码的性能与输入数字的大小有关，如果输入的数字很大，则可能会出现性能问题。但是，对于较小的数字，该代码可能比传统的质数检测算法更快。如果需要在实际应用中使用该代码，请根据具体情况进行测试和优化。

他的回答是： 对于较小的数字（比如小于 10^6），该代码通常比试除法或米勒-拉宾素性检验等传统算法更快。
具体性能怎样，还得仔细测试，毕竟ChatGPT也有可能是编的。而且这个n越大，占用内存也越大，只能当做一个小技巧，实际运用还需要注意。

结语

发散一下思维，这个正则是找某个数的倍数，那么奇数偶数也可以这样判断，那就是找2的倍数。
这就是正则有意思的地方，以前一直以为正则就是匹配特定字符串啥的，没想到这种数学思维也可以结合起来，不得不说：有点东西。

参考引用

检测质数的正则原文章
正则表达式30分钟入门教程
JavaScript 在线正则测试器
在线运行代码网站

上一页
2023-03-31 00:00:00 # 正则表达式 # 随笔
下一页