#29 演算法的威力
在我們前面的範例程式，若仔細看「因數分解」程式碼，用的是最直觀方法，當n大於2時，已知1與n必然是因數，所以用for迴圈從2一路找到n-1，看能否整除n，如果能整除，就加入「因數」陣列中：
for i in 2...(n-1) {
if n % i == 0 {
因數 = 因數 + [i]
}
}
這樣算法雖然正確，但實在太慢，分解8位數就需花十幾秒，那分解100位數(密碼學應用需100位數以上)豈不是算到宇宙滅亡！有沒有更快的方法呢？
當然有，而且還不只一種。如果反覆觀察，我們可以發現「因數分解」有以下幾個特徵，可用來「加速」程式：
- 因數都是成對出現的，如果 n / i 能整除的話（也就是 n % i == 0），除了除數 i 是因數，(n / i)的商也是因數。唯一的例外就是如果 n 是平方數，那 n 的平方根就是唯一不成對的因數。
- 不需要從2找到(n-1)整個範圍，只要找2到n的平方根即可。
舉例來說，觀察100的因數分解，100平方根是10，所以只要找 2...10能夠整除100的，再加上配對的商數即可，也就是：
(2, 50), (4, 25), (5, 20), (10)
經過重新排序，再加上 1, 100 也是因數，最後因數分解的結果就是：
[1, 2, 4, 5, 10, 20, 25, 50, 100]
這樣一來，迴圈計算的次數從原本98次（2...99）大幅降低到9次(2...10)。對於8位數20220109來說，迴圈次數會從2千萬次降低到只需4千多次，相當於將8位數縮短成4位數的計算時間！
以下我們就根據這樣的運算方法（或稱為「演算法」），重新改寫3-8b因數分解的程式：
// 3-8c 加速因數分解
// Revised by Heman, 2022/01/11
import Foundation
enum 因數分解錯誤: Error {
case 負整數
case 等於零
}
func 因數分解(_ n: Int) async throws -> [Int] {
if n < 0 { // 排除零與負數
throw 因數分解錯誤.負整數
} else if n == 0 {
throw 因數分解錯誤.等於零
} else if n == 1 {
return [1]
}
var 因數: [Int] = [1] // 1與n是基本的因數
let 近平方根 = Int(sqrt(Double(n)))
for i in 2...近平方根 {
if n % i == 0 {
因數 = 因數 + [i]
let 商數 = Int(n / i)
if 商數 != 近平方根 {
因數 = 因數 + [商數]
}
}
}
因數 = 因數 + [n]
return 因數.sorted()
}
let 某數 = [-20220109, 0, 20220109, 20220911, 123456789012345, 135791357913579]
var 時間差: Double = 0.0
let 計時開始 = Date()
print("因數分解 -- 開始時間：\(計時開始)")
for i in 某數 {
Task {
do {
let 因數 = try await 因數分解(i)
時間差 = Date().timeIntervalSince(計時開始)
print("\(i): \(因數) 時間差 \(時間差)")
} catch 因數分解錯誤.負整數, 因數分解錯誤.等於零 {
print("錯誤：僅限正整數的因數分解(\(i))")
} catch {
print("錯誤：其他原因(\(i))")
}
}
}
時間差 = Date().timeIntervalSince(計時開始)
print("[因數分解]共花費時間(秒)：\(時間差)")
print("程式結束：\(Date())")
import PlaygroundSupport
PlaygroundPage.current.needsIndefiniteExecution = true
在程式中，我們用了一個新的函式，sqrt() 用來求平方根，參數必須是實數，所以用Double(n)將整數n轉換為實數，算出平方根（實數）之後，再用 Int() 轉回整數：
let 近平方根 = Int(sqrt(Double(n)))
所以「近平方根」就是最接近（小於或等於）n平方根的整數。
接下來 for 迴圈只要從2算到「近平方根」，將可整除n的除數與商數加入到「因數」陣列中：
for i in 2...近平方根 {
if n % i == 0 {
因數 = 因數 + [i]
let 商數 = Int(n / i)
if 商數 != 近平方根 {
因數 = 因數 + [商數]
}
}
}
最後將 n 本身也加入「因數」陣列中，並且將整個陣列排序後回傳。排序用的是物件方法 .sorted()，可對陣列內容加以排序後，回傳「排序後的陣列」（所以用被動語態sorted）：
因數 = 因數 + [n]
return 因數.sorted()
最後執行結果，對3個8位數20220109, 20220911, 20223009竟然只要0.02秒多，比起上一節3-8b用16秒足足快了約800倍，比最初版本3-8a用29.2秒近1500倍！
為了檢驗新的算法，我們還特地增加一個平方數 20223009（4497的平方），以及兩個15位數的整數，全部算出來也不過花8.9秒多而已。
因數分解 -- 開始時間：2022-01-13 00:05:16 +0000
錯誤：僅限正整數的因數分解(-20220109)
錯誤：僅限正整數的因數分解(0)
[因數分解]共花費時間(秒)：0.007884979248046875
程式結束：2022-01-13 00:05:16 +0000
20223009: [1, 3, 9, 1499, 4497, 13491, 2247001, 6741003, 20223009] 時間差 0.021432995796203613
20220109: [1, 7, 13, 91, 222199, 1555393, 2888587, 20220109] 時間差 0.021718978881835938
20220911: [1, 97, 208463, 20220911] 時間差 0.0246199369430542
123456789012345: [1, 3, 5, 15, 283, 849, 1415, 3851, 4245, 11553, 19255, 57765,
1089833, 3269499, 5449165, 7552031, 16347495, 22656093, 37760155, 113280465,
2137224773, 6411674319, 10686123865, 29082871381, 32058371595, 87248614143,
145414356905, 436243070715, 8230452600823, 24691357802469,
41152263004115, 123456789012345] 時間差 8.547168970108032
135791357913579: [1, 3, 31, 37, 93, 111, 367, 1101, 1147, 1369, 3441, 4107, 11377, 13579,
34131, 40737, 42439, 127317, 420949, 502423, 1262847, 1507269, 2906161, 8718483,
15575113, 46725339, 90090991, 107527957, 270272973, 322583871,
1066561087, 3199683261, 3333366667, 3978534409, 10000100001, 11935603227,
33063393697, 39462760219, 99190181091, 118388280657, 123334566679, 370003700037,
1223345566789, 1460122128103, 3670036700367, 4380366384309,
45263785971193, 135791357913579] 時間差 8.970889925956726
只是改變一個計算方式，程式碼也沒幾行，就能加快這麼多，可見演算法的威力！
註解
- 在電腦科學(computer science)中，研究解決問題的方法與程序稱為「演算法(algorithm)」，是資訊科系必修課程，除了研究更快更好的方法之外，也研究計算困難的數學難題。
- 質因數分解與第一單元提過的費波那契數，都只用到「整數」，數學上研究整數特性的理論稱為「整數論」（或簡稱「數論」），聽起來簡單，小學生都能懂，讓人誤以為用電腦一定可以解決所有數論問題，沒什麼好研究的，其實不然。
- 2018年上海有位名叫「談方琳」的14歲小女孩，解開了一個數論的千年難題，就是研究「費波那契數」和「貝祖數（與最大公因數有關）」的關係，成為公認的數學天才，堪稱當代的高斯，就是最好例子。
- 本節的因數分解其實還不夠快，尚有很多改善空間，值得深入研究。不過演算法並非本單元課程範圍，重點還是放在「非同步模式」與「錯誤處理」。
