利用正則表達式判斷質數 (素數) 聽起來不可思議,但確實可行。本文解析這個「神人」寫法的原理:將數字轉為一進制字串,配合回溯參考 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
String(i, "1") 產生長度為 i 的「1」字串:
"1""11""111""1111""111111"^1?$ # 匹配 0 或 1 (非質數)
| # 或
^(11+?)\1+$ # 匹配可被整除的合數
(11+?):非貪婪匹配「至少兩個 1」的最短子串 (代表潛在除數 k ≥ 2)。\1+:回溯參考,要求該子串重複 1 次以上 (代表被除數 = k × m, m ≥ 2)。k × m (k≥2, m≥2) = **合數**。If Not regex.Test(...) → **不匹配 Pattern = 質數**。
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 時極慢甚至凍結。**切勿用於生產環境**。
雖非實用演算法,但這個正則表達式是理解「計算理論邊界」與「正則回溯機制」的絕佳教材。