萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

VBScript 正則表達式判斷質數:神奇的一行 Pattern 解析

利用正則表達式判斷質數 (素數) 聽起來不可思議,但確實可行。本文解析這個「神人」寫法的原理:將數字轉為一進制字串,配合回溯參考 Pattern 檢測可被整除。

核心代碼

Set regex = New RegExp
regex.Pattern = "^1?$|^(11+?)\1+$"

For i = 1 To 100
  If Not regex.Test(String(i, "1")) Then
    WScript.Echo i
  End If
Next

原理解析

步驟 1:數字 → 一進制字串

String(i, "1") 產生長度為 i 的「1」字串:

  • 1 → "1"
  • 2 → "11"
  • 3 → "111"
  • 4 → "1111"
  • 6 → "111111"

步驟 2:Pattern 拆解

^1?$          # 匹配 0 或 1 (非質數)
|             # 或
^(11+?)\1+$   # 匹配可被整除的合數
  • (11+?):非貪婪匹配「至少兩個 1」的最短子串 (代表潛在除數 k ≥ 2)。
  • \1+:回溯參考,要求該子串重複 1 次以上 (代表被除數 = k × m, m ≥ 2)。
  • 整體匹配成功 = 字串長度可表示為 k × m (k≥2, m≥2) = **合數**。

步驟 3:邏輯反轉

If Not regex.Test(...) → **不匹配 Pattern = 質數**。

執行結果 (1-100 質數)

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

效能與實用性

方法時間複雜度實用性
試除法O(√n)高,通用演算法
正則表達式指數級 (回溯)極低,僅供展示/教學

警告: 此正則屬於「病態回溯」模式,i > 1000 時極慢甚至凍結。**切勿用於生產環境**。

延伸思考

  • 正則表達式本質上是有限狀態機,質數判斷需要計數能力,超出正則理論表達力 (需上下文相關文法)。
  • 此技巧利用「一進制字串長度」將算術問題轉為字串模式匹配,展示了計算模型間的有趣映射。
  • 來源:demon.tw、enun.net

雖非實用演算法,但這個正則表達式是理解「計算理論邊界」與「正則回溯機制」的絕佳教材。

copyright © 萬盛學電腦網 all rights reserved