【TIS-100 攻略】TIS-NET 第 21 關(guān)：質(zhì)因數(shù)計算器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。
TIS-NET 第 21 關(guān)《質(zhì)因數(shù)計算器》（Prime Factor Calculator）關(guān)卡展示
本關(guān)要求列出 IN 里提供的數(shù)字的所有質(zhì)因數(shù)，將這些質(zhì)因數(shù)依次輸出，并以 0?作為結(jié)束標(biāo)記。IN 里的數(shù)字一定在 2~99 范圍內(nèi)。
我們首先想到的是將 2~99 中的所有質(zhì)數(shù)列出來，并令原數(shù)依次和這些數(shù)做除法運算，檢查能否被指定的質(zhì)數(shù)整除。但是 2~99 范圍內(nèi)有 25 個質(zhì)數(shù)，一個節(jié)點根本寫不下。我們必須要想辦法縮減這張質(zhì)數(shù)表的大小。
這里先說一個結(jié)論：2~99 范圍內(nèi)的數(shù)，要么是質(zhì)數(shù)，要么一定能被 2、3、5、7 中的任何一個數(shù)整除。因為不含 2、3、5、7 這四個質(zhì)因子的最小合數(shù)為 11×11=121。因此原始數(shù)字我們只需要判斷是否能被 2、3、5、7 整除即可。2~99 范圍內(nèi)，如果一個數(shù)字不能被 2、3、5、7 中的任何一個數(shù)整除，那么它要么是 1，要么是質(zhì)數(shù)。我們的質(zhì)數(shù)表里只需要列出 2、3、5、7 這四個質(zhì)數(shù)就 OK 了。
本題的算法如下：
從 in 讀入一個數(shù)字 a；
檢查 a 能否被 2 整除，若能，則將 a 除以 2，并向輸出口輸出 2 這個因子，然后反復(fù)執(zhí)行此步，直到 a 不能被 2 整除為止；
檢查 a 能否被 3 整除。若能，則將 a 除以 3，并向輸出口輸出 3 這個因子，然后反復(fù)執(zhí)行此步，直到 a 不能被 3?整除為止；
檢查 a 能否被 5 整除。若能，則將 a 除以?5，并向輸出口輸出 5?這個因子，然后反復(fù)執(zhí)行此步，直到 a 不能被 5 整除為止；
檢查 a 能否被 7 整除。若能，則將?a?除以 7，并向輸出口輸出 7 這個因子，然后反復(fù)執(zhí)行此步，直到 a 不能被 7?整除為止；
至此，a 不是 1 就是一個大于 7 的質(zhì)數(shù)。僅當(dāng) a 不為 1 時，輸出最后的 a。
本關(guān)的代碼如下：
上方節(jié)點首先將本輪的 a 向下傳（mov up down），并不斷提供 2、3、5、7 的質(zhì)因子（mov 2 down, mov 3 down, mov 5 down, mov 7 down），用于檢查 a 是否能被這些數(shù)整除。最后提供一個 0 的結(jié)束信號（mov 0 down）。
中央節(jié)點依次計算 a 能否被 2、3、5、7 整除：
它將收到的 a 放入 bak（mov up acc）
（swp）
并從上方的質(zhì)數(shù)表里讀入一個 b，放入 acc（mov up?acc）。
如果從上邊收到了 0，說明到達(dá)了質(zhì)數(shù)表的末端，跳到第 13 行執(zhí)行（jez d）。
尚未收到 0 時，將 b 和 a 依次發(fā)給右邊的節(jié)點（mov acc right）
（swp）
（mov acc right），讓右邊計算 a 能否被 b 整除，并接收右邊的反饋信號：
當(dāng) a 不能被 b 整除時，你會收到 -6 信號，此時向上跳 6 行，從質(zhì)數(shù)表里讀入一個新的 b，然后計算 a 能否被新的 b 整除。
當(dāng) a 能被 b 整除時，你會收到 1 信號，同時右邊會把 a 除以 b 的商 q 發(fā)過來。此時向下跳 1 行，用 q 覆蓋 a（mov left acc），
并將當(dāng)前的有效質(zhì)因子?b（swp）
向下發(fā)送（mov acc down）。
最后跳回第 5 行繼續(xù)計算新的 a 能否被 b 整除（jmp 5）。
如此反復(fù)，直到所有的質(zhì)因子 b 都被嘗試過了以后，a 會變成 1 或一個大于 7 的質(zhì)數(shù)。此時跳到第 13 行，將最后的 a（swp）
向下發(fā)送（mov acc down）。
右邊的兩個節(jié)點用于配合計算 a 除以 b 的值。其中中間靠右的節(jié)點用來計算余數(shù) r，右下角的節(jié)點用來反復(fù)提供除數(shù) b，以及計算商 q。
中間靠右的節(jié)點將收到的除數(shù) b 發(fā)給左下角（mov left?down），
然后將被除數(shù) a 放入 acc，作為 r 的初始值（mov right acc）。
接下來，每將 r?減去一次 b（sub down），
就判斷 r?的符號。是正號時按順序執(zhí)行，是負(fù)號時跳到第 12 行（jlz?c），
是 0 時跳到第 8 行（jez 8）。
r 是正號時，向下發(fā)送 -4 讓下方保留住當(dāng)前的 b（mov -4 down），
然后跳回第 3 行繼續(xù)減（jmp 3）；
r 是 0 時，說明 a 能被 b 整除，向下發(fā)送 1 令下方將當(dāng)前的商傳上來（mov 1 down），
向左發(fā)送 1 表示當(dāng)前因子有效（mov 1 left），
并將得到的商 q 一并發(fā)給左邊，作為下一輪的 a（mov down left）；
（jmp 1）
r 是負(fù)號時，說明 a 不能被 b 整除，向左發(fā)送 -6 表示當(dāng)前因子無效（mov -6 left），
向下發(fā)送 3 令下方將本輪的 b 和?q 丟棄（mov 3 down）。
現(xiàn)在來看反復(fù)提供除數(shù)以及計算商的右下角節(jié)點：
右下角的節(jié)點收到 b 后（mov up acc），
每發(fā)送一次 b（mov acc up），
就令 bak 里的商 q 加上 1（swp）
（add 1）
（swp）
然后聽從上方的指令（jro up）：收到 -4 時，說明當(dāng)前除法尚未計算完成。我們保留住當(dāng)前的 b 和 q，向上跳 4 行，繼續(xù)執(zhí)行發(fā)送 b 和 q+1 的任務(wù)；
收到 1 時，說明 a 能被 b 整除。我們向下跳 1 行，將計算好的 q（swp）
發(fā)給上方（mov acc up），作為下一次除法計算的 a 值，然后清除 b?和 q。
收到 3 時，說明 a 不能被 b 整除。我們向下跳 3 行，直接清除掉本輪的 b（sub acc）
和 q（swp）
最后是下方居中的輸出節(jié)點。這個節(jié)點會不斷收到正中央傳來的 1 或質(zhì)因子。如果收到的是 2、3、5、7 中的一個，說明還有 1 或別的質(zhì)因子，我們不能輸出末端的 0。直到收到最終的 1 或一個大于 7 的質(zhì)因子時，我們才能輸出末端的 0。我們依次檢查：
如果收到的數(shù)字是 1（mov -1 acc）
（add 1）
則不輸出該 1，直接跳到第 8 行輸出序列末端的 0（jez 8, mov 0 down）。
收到的數(shù)字是大于 1 的數(shù)字時，說明這是一個質(zhì)因子，我們將其輸出（add 1）
（mov acc down）
然后緊接著判斷：如果該質(zhì)因子是 2、3、5、7 中的一個，則尚未到達(dá)序列末端。因此，如果該質(zhì)因子小于 11（sub 11），
則跳回第 1 行繼續(xù)等待下一個質(zhì)因子（jlz 1），
直到得到了 1 或一個大于等于 11 的質(zhì)因子后，我們輸出序列末端的 0（mov 0 down）。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
