從ACM回來的數學題（二）

題外話1：大家有留意的話，這個blog是由一班數學資料庫成員合作而寫的。昨日的數學資料庫例會之後，我們的作者名單增加了四個人。可以預料手記的更新將會更為頻密，為廣大網友提供更多的數學資訊。

題外話2：數學資料庫在昨日下午已經換上全新的主頁設計。自己覺得這個設計蠻好的。以往的設計需要網友們scroll down才能見到每一個項目的更新，現在則不用了。而主頁那種顏色的配搭我覺得還真美的。在此要感謝MD的會員Vris花了很多時間去設計這個新主頁。

---

入正題。上回預告，今次講第二題。

越南Danang的ACM/ICPC Problem C。題目是這樣的：我們稱一組連續k個質數為一個「k質數組」。例如(31,37)是一個「2質數組」，(83,89,97)是一個「3質數組」，而(53,61)則不是「2質數組」，因為53和61之間還有一個質數59。而每一個「k質數組」的重量就是該k個質數中最大的質數和最少的質數之差。例如(11,13,17,19,23)就是一個重量為23-11 = 12的「5質數組」。現在給出a,b符合條件1 < a < b < k 和 d ，要找出在 [a,b] 內有多少個重量為d的「k質數組」。

當時想了一想，如果test case當中有 d = 0 ， k = 1，那不就是問我 a和b之間有多少個質數嗎？若然 a 和 b 均是很大的數，那麼要得到一個好的估計還不難（就是用Prime Number Theorem吧），但要無誤差地說出在某個特定的range內有多少個質數，唯一已知的方法就是逐個試。

最後因為a和b太大，我們認為TLE（Programming Contest術語，全寫為Time Limit Exceeded）的可能性非常大，所以我們没有做。比賽完畢後，相信百多隊中只有兩隊能夠完成這題，而其中一隊是相熟的中山大學隊。一問之下，才知道要用一個Radin-Miller Primality Test。

一般情況下，如果給的數n不太大的話，我們慣了用以下的以下的algorithm去驗它是否質數：

1)
If n is even but not 2, then it is NOT prime, done and leave this procedure.

2) for (i=3 ; i<=sqrt(n); i+=2) if (n mod i = 0) then n is NOT prime, done and leave this procedure.

3) n is a prime, terminate.

上面的algorithm的基礎就是基於一個定理：如果 n 是合成數，它最小質因數必然 <= sqrt(n)。稍為認識analysis of algorithm的人都應該知道這個 algorithm的run time是O(sqrt(n))。如果 n 是一個八位數，那麼用這個 algorithm 去驗証 n 是否質數，就需要試最少三千多次。若然只做一兩次還好，但若然有十萬個八位數要你試，最壞情況要試過億次。別以為現在的CPU越來越快，要這樣試，我辦公室內的電腦已經比一般家用電腦快，都要大約8.75秒。而這道比賽題目極有可能有test case需要我們試一千萬個數，所用的時間粗略估計會是8.75秒的20至100倍。而比賽的程式運行時間是有限制的，一般來說不會超過一分鐘。所以這個方法是不可以用來解決這道題目的。

Radin-Miller Primality Test的概念是這樣的。如果 n 是一個質數，那麼根據費馬小定理，對於所有 a < n，都有 a^n-1 = 1 (mod n)。若把 n-1 表成 2^s d（d是奇數），我們可以得到

a^d = 1 (mod n)

或

a^{2^r d} = -1 for some 0 <= r <= s-1

Radin-Miller Primality Test就是使用以上定理的contrapositive。只要我們找出一個 a 使得以上兩條等式均不成立，那麼 n 就不可能是質數。當然，要找出一個這樣的 a 也不見得容易。但後來有人證明了對於少於 2,152,302,898,747 的 n ，只要試 a = 2, 3, 5, 7 或 11，若然對於這五個 a 的數值，都可以符合以上定理中兩組等式的其中一組，那麼 n 就是一個質數了。

就是因為這個結果，對於每個 n 驗證是否質數的時間就變成了 5 lg n。若 n 是一個八位數字，那麼最多大約要做135次，比起上面那個"naive algorithm"的過3000次好太多了。

用了這個Radin-Miller Primality Test後怎樣完成餘下的部分就不算難，有興趣的讀者可以自己想想。

說回比賽。原來我其中一個組員是知道這個primality test的，但他當時覺得用了這個test後程式運行時間仍然太大，所以決定放棄。無言。