写在前面

最近看到一篇很有意思的文章¹ (是看阮一峰老师的科技周刊的一个部分), 是采用正则表达式进行素数匹配的, 很简练的几个符号, 但是却很有用, 下面用python分析一下然后给出代码实现.

代码与分析

import re


def isPrime(N):
    rex = re.compile(r"^1?$|^(11+?)\1+$")
    return True if not re.match(rex, "1" * N) else False


if __name__ == '__main__':
    k = 0
    N = 100
    for i in range(1, N + 1):
        if isPrime(i):
            print(i, end=" ")
            k += 1
    print()
    print(f"The number of prime in 1~{N} is: {k}")

'''
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
The number of prime in 1~100 is: 25
[Finished in 55ms]
'''

这里主要的思路就是匹配不是质数的数字.

方法是先生成待判断的数字长度的一个字符串, 这里以N*'1'为例, 然后进入正则表达式r"^1?$|^(11+?)\1+$"进行判断, 由于这个表达式分成了两部分, 这里就分两块进行分析.

第一部分(边界条件)

^1?$

由于0,1都不是素数, 这里就要先针对''和'1'进行判断, 使其满足表达式的匹配即可.

思路就是看字符串是不是以1开头(如果字符串有值), 这里主要的精髓就是?, 用来匹配一个字符或没有字符.

第二部分(主要部分)

^(11+?)\1+$

这里就是整个表达式匹配最核心的部分了, 乍一看感觉没什么内涵, 但是其实这短短的几个字符就蕴含了一个程序设计中的主要思想:回溯(递归实现).

试想一下, 对于一个任意长度的各字符完全相同的字符串, 要想判断长度是否是一个质数\合数, 当然就要看其因子, 如果其长度能被2,3,5,...整除, 那显然就是合数了.

在正则表达式中, 如果想要匹配满足这样条件的字符串, 首先应该对其作分组处理, 从'11'这个字符串开始, 一点一点判断,如果匹配了, 那当然就能说这个字符串代表的数字为合数了.

正则表达式的一个很好的机制就是首尾的判断, 加上$, 就意味着如果分组不满足匹配, 则进入下一层接着找, 直到找到最后一种, 才进行结果的返回, 在这里就是将前面的11作为一个因子, 看后面的部分里面有没有11这个因子, 如果有, 就是合数, 如果没有, 引擎进入下一层的判断, 将前面的(11+?)扩展为111, 并进入下一层匹配, 以此类推..

注意:

• 第二部分的字符?是必要的, 因为这样可以采用正则表达式的非贪婪模式进行匹配, 只要找到一个因子, 就可以进行判断并返回. 如果不加的话, 就会一直匹配到最后的因子, 这样会让匹配效率大打折扣.

  打个比方²：我们匹配12。^.?$|^(..+)\1+$会做的事情是先判断12是不是11的倍数、then 12是不是10的倍数……..then 12是不是6的倍数。^.?$|^(..+?)\1+$会做的是先判断12是不是2的倍数，then 就没then了。对于素数的效率是一样的，因为每个位置都需要匹配过来，但是对于非素数从小开始匹配则能够让这个表达式早点结束匹配。

  在上述程序中, 采用10000个测试用例, 加问号的话所用时长为18.3s, 而不加问号就是67.7s, 可见其对效率的影响还是很大的.

• 上面的程序可以重写为:

  def isPrime(N):
      rex = re.compile(r"(?!^1?$|^(11+)\1+$)")
      return True if re.match(rex, "1" * N) else False
      
  

  看起来不如上面的直观, 采用了反向匹配的方式.

  (?! ), 表示否定性前瞻断言，即若括号内容不匹配，则.group()返回括号前面匹配到的字符.