在國小到高中課堂上教的數學裡，其實隱含許多的演算法在裡頭，只不過在用人腦解題時，不像電腦一樣需要很明確的流程，甚至有時會根據直覺簡化或改變計算過程，因此不一定會意識到正在使用的方法事實上是一個演算法，或是不一定能馬上將作法轉換成電腦可以使用的演算法。
這個章節會透過一些國小到高中的數學課上提到的問題，帶領讀者將在學校課綱內學到的知識，結合枚舉、搜尋等章節的內容，從基礎的數學發現演算法。
要找出一個數 $x$ 的因數，根據因數的定義「$y$ 是 $x$ 的因數代表 $x$ 除以 $y$ 是整數」來看，最直接的方法就是枚舉 $1$ 到 $x$ 的所有整數 $y$，看看 $x$ 除以 $y$ 的餘數是不是 $0$。
for (int y = 1; y <= x; y++) {
if (x % y == 0) {
// y 是 x 的因數
}
}
這樣要一一枚舉 $1$ 到 $x$ 之間的共 $x$ 個數字，時間複雜度是 $O(x)$。
那麼我們是怎麼用人腦找出因數的呢？在用人腦找出一個數的因數的時候，可能會是列出像這樣的式子：
$$
\begin{align*}
36 &= 1 \times 36 \\
&= 2 \times 18 \\
&= 3 \times 12 \\
&= 4 \times 9 \\
&= 6 \times 6 \\
&= \color{gray}{9 \times 4} \\
&= \color{gray}{12 \times 3} \\
&= \color{gray}{18 \times 2} \\
&= \color{gray}{36 \times 1}
\end{align*}
$$
也就是找出所有 $x$ 拆成兩個數字乘積的方法，裡面出現的所有數字就是全部的因數了。老師可能還教過一個技巧：如果是按照左邊那個數字由小到大去找，只要找到左邊數字 $>$ 右邊數字，那麼就不用再找了，因為現在這個和接下來所有的拆分方式，其實都已經在前面出現過了，只是兩個數字交換而已。
因此，我們可以從本來一一枚舉可能的因數，換成枚舉可能的拆分方式。既然左邊數字 $>$ 右邊數字的拆分方式，我們都不需要，這代表我們只需要找出所有滿足 $y \leq x/y$，也就是 $y^2 \leq x$ 的因數 $y$ 作為拆分方式們的左邊數字就好了。
將這個過程翻譯成程式碼的話就會是：
for (int y = 1; y * y <= x; y++) {
if (x % y == 0) { // x = y * (x / y)
// y 是 x 的因數
// x / y 是 x 的因數
// y 跟 x / y 可能是相同的，如果不能重複處理的話要特別注意
}
}
$y^2 \leq x$ 的意思就是 $y \leq \sqrt{x}$，我們的時間複雜度就跟著枚舉的數字數量一起變成 $O(\sqrt{x})$ 了！
不要把 y * y <= x 寫成 y <= sqrt(x)，因為 sqrt(x) 的結果是浮點數，可能會有浮點數誤差。
在會尋找因數後，檢驗一個數字是不是質數就很簡單了：只要 $x$ 的因數只有 $1$ 和 $x$，那它就是一個質數，反之則不是。因為質數唯一滿足「左邊數字 $\leq$ 右邊數字」的拆分方式就只有 $1 \times x$，我們可以檢查它有沒有別種的拆分方式，有的話就代表它不是質數。
bool is_prime(int x) {
for (int y = 2; y * y <= x; y++) { // 起始值是 2
if (x % y == 0) { // x = y * (x / y)
return false;
}
}
return true;
}
在這一節中，我們只討論對 $\geq 1$ 的數字開根號，因為 $<1$ 的數字開根號後會變大，需要多處理一些瑣碎的條件。
在學到開根號的時候，同時也會學到一種手動計算開根號的方法：十分逼進法。具體來說，就是一一找到答案每一個位數的數值，舉個例子，我們要計算 $\sqrt{2}$，因為 $2$ 的最高位數在個位數，$\sqrt{2}$ 的最高位數肯定也不會超過個位數，因此我們找找看個位數是多少：
$$
0^2=0 \leq 2 \qquad 1^2=1 \leq 2 \qquad 2^2=4>2
$$
所以說 $\sqrt{2}$ 在 $1$ 和 $2$ 之間，我們就知道了它的個位數是 $1$。接著我們再看看下一個位數，也就是小數點後第一位：
$$
\begin{align*}
1.0^2 &= 1.00 \leq 2 \\
1.1^2 &= 1.21 \leq 2 \\
1.2^2 &= 1.44 \leq 2 \\
1.3^2 &= 1.69 \leq 2 \\
1.4^2 &= 1.96 \leq 2 \\
1.5^2 &= 2.25 > 2
\end{align*}
$$
在經歷了有一點多的計算之後，得到 $\sqrt{2}$ 在 $1.4$ 和 $1.5$ 之間，所以小數點後第一位是 $4$。像這樣子不斷加一個位數，從 $0$ 試到 $9$，找到平方後 $\leq 2$ 的最大那一個就是答案的這一個位數。如此一來就可以得到越來越精確的 $\sqrt{2}$ 的數值。
硬是把十分逼進法轉換成程式碼的話，就會是：
double sqrt(double x) { // 假設 x >= 1
// 想辦法找到 x 的最高位數
// 例如 x=123 時 t 會是 100、x=0.01 時 t 會是 0.01
double t = 1;
while (t * 10 <= x) t *= 10;
// 假設我們想找從 x 的最高位數開始的前 10 個位數
double ans = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j <= 9; j++) {
// 如果把現在看的位數 +1，平方後不會超過 x，那就加上 1
if ((ans + t) * (ans + t) <= x)
ans += t;
}
t /= 10;
}
return ans;
}
這個作法不僅對人類來說很費力，對電腦而言好像也有點複雜。其實我們在自己計算十分逼進法時，不一定要乖乖地從 $0$ 數到 $9$，而是有時候某些太大或太小的數字顯然就不可能，可以直接跳過，也可以直接先檢查 $5$ 看看答案是更大還是更小，這樣才不會在答案是 $9$ 的時候還要把所有數字都檢查一遍。
「先檢查 $5$ 看看答案是更大還是更小」這不就是二分搜尋法嗎？回顧一下剛剛的例子
$$
\begin{align*}
1.0^2 &= 1.00 \leq 2 \\
1.1^2 &= 1.21 \leq 2 \\
1.2^2 &= 1.44 \leq 2 \\
1.3^2 &= 1.69 \leq 2 \\
1.4^2 &= 1.96 \leq 2 \\
1.5^2 &= 2.25 > 2
\end{align*}
$$
在這個位數是一些比較小的數字的時候，平方會 $\leq 2$，而到比較大的數字就會變成 $>2$，我們要的是 $\leq 2$ 和 $>2$ 的交界處，正好就是二分搜尋法可以快速做到的事情！
這讓人類手算時可以省一些功夫，但寫成程式碼就有點累人了。先不要急著直接把這個作法變成程式碼，既然二分搜尋法可以幫我們找某個位數，那不是直接讓二分搜尋法幫我們找答案就好了嗎？！
double sqrt(double x) { // x >= 1
double l = 0, r = x; // 一開始的搜尋範圍是 [1, x]
for (int i = 0; i < 30; i++) { // 看要搜尋幾次，越多次越精確
double mid = (l + r) / 2;
if (mid * mid <= x) l = mid;
else r = mid;
}
return l;
}
其實十分逼進法在設計上還是有一點考量到人類計算的方便性，因為大多數人都比較習慣十進位，才會用「十」分逼進法。但以寫程式而言，電腦並沒有像人一樣難以計算多位數四則運算的問題，因此流程簡單才是最重要的，從上面的程式碼就可以看得出來，不斷分兩半當然會比每一位數分開處理，再把每一位數分十半簡單好寫。
事實上 <cmath> 中的 sqrt 就已經很快速和精確了，在需要浮點數的答案時可以直接使用，不過在需要的是 $\lfloor \sqrt{x} \rfloor$ 這樣取整數後的數值時（$\lfloor \sqrt{x} \rfloor$ 是下高斯記號，代表 $\leq x$ 的最大整數），就可以考慮自己用二分搜尋法實作，以避免浮點數誤差，也節省浮點數運算需要的時間。
剛剛才說到電腦沒有像人一樣難以計算多位數四則運算的問題，但遺憾的是 C++ 的 int、long long、double 等等數字形態都有數字範圍的上限，當真的需要使用非常多位數的數字的時候，就得要想辦法自己寫運算了。
這個章節的主要目的是引導讀者將平常人類計算的方法轉換成程式，因此會著重在以簡潔的方式實作，比較不在乎要讓程式有效率地運作。
要儲存一個很大的數字，我們可以用一個陣列把每個位數分開存，
像是用一個長度為 $k$ 的陣列 $a_0,a_1,\dots,a_{k-1}$ 中的 $a_i$ 代表右邊數來第 $i$ 個位數（最右邊是第 $0$ 個位數），
這個陣列代表的數字就是 $a_0 \times 10^0 + a_1 \times 10^1 + a_2 \times 10^2 + \dots + a_{k-1} \times 10^{k-1}$，
這樣一來最大可以存的數字是 $9 \times 10^0 + \dots + 9 \times 10^{k-1} = \underbrace{999\dots999}_k = 10^k-1$。
// 用陣列儲存數字的每一位數，這裡的陣列第 i 個元素是 10^i 的那個位數
int a[len] = {3, 6, 7, 8, 4, 0, 0, 0, 0, 0}; // 48763
int b[len] = {4, 7, 4, 1, 2, 0, 0, 0, 0, 0}; // 21474在一開始學到加法的時候，就會學到用直式計算加法，像是：
$$
\begin{array}{cccccc}
& \small1 & \small1 & \small1 & & \\
& 4 & 8 & 7 & 6 & 3 \\
+& 2 & 1 & 4 & 7 & 4 \\ \hline
& 7 & 0 & 2 & 3 & 7
\end{array}
$$
在計算的時候，我們會把兩個要相加的數字的個位數對齊，寫下來後，從最右邊的位數開始計算。當計算某個位數時，把那一直行的數字都加起來，結果的個位數就是答案，而如果加起來的數字不只一個位數，就是「進位」了，把十位數寫到左邊那一直行的最上面去。
const int len = 10; // 數字的最大位數（答案也不能超過這個位數）
void big_plus(int a[len], int b[len], int c[len]) { // c = a + b
int carry = 0; // 上一個位數進位到這一位數
for (int i = 0; i < len; i++) {
int sum = a[i] + b[i] + carry; // 兩個數字的這一位數相加，再加上進位
c[i] = sum % 10; // 總和的個位數就是答案
carry = sum / 10; // 超出個位數的部分要進位到下一個位數
}
}
void plus_test() {
// 用陣列儲存數字的每一位數，這裡的陣列第 i 個元素是 10^i 的那個位數
int a[len] = {3, 6, 7, 8, 4, 0, 0, 0, 0, 0}; // 48763
int b[len] = {4, 7, 4, 1, 2, 0, 0, 0, 0, 0}; // 21474
int c[len]; // 答案
big_plus(a, b, c);
for (int i = len - 1; i >= 0; i--)
cout << c[i];
cout << endl; // 0000070237
}加法會有「加起來太多了，所以進到下一個位數」的問題，不過就只要把進位的部分丟給下一位數煩惱就好，不難處理。減法則有「上面的數字比下面的數字小，需要跟左邊的位數借位」的問題，這就比加法的進位稍微複雜一點了，像是這樣的狀況：
$$
\begin{array}{cccccc}
& \small1 & \small9 & \small9 & \small9 & \small{10} \\
& \not2 & 0 & 0 & 0 & 0 \\
-& & & & & 1 \\ \hline
& 1 & 9 & 9 & 9 & 9
\end{array}
$$
在計算 $20000-19999$ 的個位數時，根據小時候學到的直式減法，因為 $0<1$，所以就要去向左邊的位數借位。然而，左邊那一個位數並不總是借得到，當左邊那位是 $0$ 就沒東西可借了，所以就要往左找到第一個不是 $0$ 的位數，幫它減 $1$、中間的人加上 $9$、現在這一位加上 $10$，才能完成借位。
程式要是寫起來的話，會比剛剛的加法複雜許多，有沒有對程式來講更簡單的作法呢？既然加法可以直接把進位的部分丟給左邊那一位煩惱，那減法可不可以也把借位丟給左邊那一位煩惱？答案是可以，借位的目的是「從高位那裡拿到 $10$」，所以乾脆把左邊那個人扣 $1$（等值於這一位的 $10$），也就是可以看成是進位 $-1$，它自己扣到負的再自己想辦法就好。
void big_minus(int a[len], int b[len], int c[len]) { // c = a - b
int carry = 0; // 上一個位數進（借）位到這一位數
for (int i = 0; i < len; i++) {
int sum = a[i] - b[i] + carry; // -10 <= sum <= 9
if (sum < 0) carry = -1, sum += 10; // 變負的要借位
else carry = 0;
c[i] = sum; // 現在 0 <= sum <= 9
}
}
void minus_test() {
int a[len] = {0, 0, 0, 0, 2, 0, 0, 0, 0, 0}; // 20000
int b[len] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}; // 1
int c[len]; // 答案
big_minus(a, b, c);
for (int i = len - 1; i >= 0; i--)
cout << c[i];
cout << endl; // 0000019999
}和前面一樣，我們來想想直式乘法是怎麼計算的：
$$
\begin{array}{ccccccccc}
&&&& 1 & 2 & 3 & 4 & 5 \\
\times&&&& & & 8 & 7 & 6 \\ \hline
&&&& 7 & 4 & 0 & 7 & 0 \\
&&& 8 & 6 & 4 & 1 & 5 & \\
&& 9 & 8 & 7 & 6 & 0 & & \\ \hline
& 1 & 0 & 8 & 1 & 4 & 2 & 2 & 0
\end{array}
$$
在兩條線中間的部分，三行依序是 $12345$ 乘上 $6,7,8$ 後的結果，其實就是把上面的數字分別乘上下面數字的每一位數，再把這些結果加總。所以要會計算「很多位數乘很多位數」的答案，就要先會算「很多位數乘一個位數」。
套用相同的「分開位數」的概念，算很多位數乘一個位數的乘法時，就是一一計算前者的每個位數乘上那一個位數是多少，最後再加總起來。因此，我們計算直式乘法的過程其實是：把兩個數字的每一位分別相乘，再把它們都加起來。
過程其實就是加法，就只是我們每次都是「把答案的第 $i+j$ 位加上 $a$ 的第 $i$ 位乘上 $b$ 的第 $j$ 位」（位數是從 $0$ 開始數！），如果加起來的結果 $\geq 10$，超出個位數的部分就進到下一個位數去。
void big_multiplies(int a[len], int b[len], int c[len]) { // c = a * b
for (int i = 0; i < len; i++) c[i] = 0;
for (int i = 0; i < len; i++) {
int carry = 0;
for (int j = 0; i + j < len; j++) {
// 從低位做到高位就能好好處理進位
// (a[i] * 10^i) * (b[j] * 10^j) = (a[i] * b[j]) * 10^(i+j)
int sum = c[i + j] + a[i] * b[j] + carry;
c[i + j] = sum % 10;
carry = sum / 10;
}
}
}
void multiplies_test() {
int a[len] = {5, 4, 3, 2, 1, 0, 0, 0, 0, 0}; // 12345
int b[len] = {6, 7, 8, 0, 0, 0, 0, 0, 0, 0}; // 876
int c[len]; // 答案
big_multiplies(a, b, c);
for (int i = len - 1; i >= 0; i--)
cout << c[i];
cout << endl; // 0010814220
}在講除法之前，要先插播一個不是四則運算的東西：比大小。
平常我們看到兩個數字的時候，應該一眼就能比較它們的大小了。具體來說，就是把兩個數的個位數對齊（我們儲存大數的方式會在高位數補上 0，而且陣列是個位數放在前面，因此自然就對齊了）後，從最高位開始比較，第一個不一樣的位數就決定了它們的大小關係：
int comp(int a[len], int b[len]) { // -1: a < b, 0: a = b, 1: a > b
for (int i = len - 1; i >= 0; i--) {
if (a[i] < b[i]) return -1;
else if (a[i] > b[i]) return 1;
}
return 0;
}總算到了四則運算裡最困難的除法。除法和加減乘很不一樣，在算加減乘法的時候，我們總是會先去算最低那個位數，然而，在算除法的時候，我們都是先找出最高那個位數是多少。
$a \div b$ 的最高位數，就是「$b$ 乘上它不會超過 $a$」的最大的數字，而這個數字也不是很好找，對人類而言只能猜猜看，好在電腦要一個一個慢慢試沒有那麼困難。在找到最高位數後，就把 $a$ 減去 $b$ 乘上它，接下來再找下一個位數。
具體來說，要怎麼找到最大的位數呢？如果我們現在要找到的位數是 $10^i$ 那一位，那我們要找的就是最大的 $d$ 使得 $d \times 10^i \times b \leq a$，乍聽之下我們會需要枚舉 $d$，用乘法算出左邊那一項，再跟 $a$ 比大小，就像前面提到的十分逼進法那樣。
其實不用那麼麻煩，也可以每當 $a \geq b \times 10^i$ 時，就把 $a$ 減去 $b \times 10^i$，看可以減幾次，那就是 $d$ 了，寫起來會簡單一些。
void big_divides(int a[len], int b[len], int c[len], int r[len]) { // a / b = c ... r
int t = len - 1;
for (; t >= 0 && b[t] == 0; t--); // 找到 b 的最高非 0 位數
int tmp[len];
for (int i = 0; i < len; i++) r[i] = a[i], c[i] = 0;
for (int i = len - t - 1; i >= 0; i--) {
// 從最大的位數開始找，要確保 b * 10^i 位數不會超過 len
int d = 0;
for (int j = 0; j < len; j++) tmp[j] = 0;
for (int j = 0; j <= t; j++) tmp[i + j] = b[j]; // tmp = b * 10^i
while (comp(r, tmp) >= 0) { // r >= tmp
big_minus(r, tmp, r); // r = tmp - r
d++;
}
c[i] = d;
}
}
void divides_test() {
int a[len] = {5, 4, 3, 2, 1, 0, 0, 0, 0, 0}; // 12345
int b[len] = {6, 7, 8, 0, 0, 0, 0, 0, 0, 0}; // 876
int c[len]; // 商數
int r[len]; // 餘數
big_divides(a, b, c, r);
for (int i = len - 1; i >= 0; i--)
cout << c[i];
cout << endl; // 0000000014
for (int i = len - 1; i >= 0; i--)
cout << r[i];
cout << endl; // 0000000081
}上面的程式碼用到了 big_minus(r, tmp, r)，其中的輸入和答案的位置是一樣的，上面的實作方式在這種情況可以正常運作，不過在遇到這種狀況時都要特別注意一下，像是上面的乘法實作方式就不能這樣。
在看過這幾個在學校課堂上常見的數學問題之後，希望讀者有稍微體會到「人腦解題」與「電腦解題」的差異之處。許多在學校數學課上學到的作法，其實都是為了讓人類方便運算，盡可能減少需要對複雜的數字計算的機會，因而有比較複雜但之於人類並不麻煩的運算流程，在轉換成演算法時，就可以忽略那些為了方便人類計算而做的設計，轉而把注意力放在寫出清晰簡潔的流程。
正整數加減乘除大數運算。
給兩個矩陣，輸出相乘後的結果。
給一個最高五次的多項式，求所有實數根在哪兩個連續整數之間，或判斷有無限多根或沒有實數根。