---

本題十分的簡單，絕對不像坊間所說的「a007 根本毒瘤質數判斷題」，相信各位在閱讀完本篇題解後必定能夠解開這題的。

小弟有七個方法可以解開這題，以下將詳細的一一介紹。

---------------------------------------------------------------------------------------

一、米勒 - 拉賓算法 (Miller-Rabin Primilarity Test)

先備知識：

(一)、費馬小定理

(二)、快速冪

 

詳細介紹去網路上 Google

https://zh.wikipedia.org/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C

---------------------------------------------------------------------------------------

二、線性篩法建表 (Linear Sieve)

先備知識：線性篩法

引理一：對於任意整數 N，若是從 [1,sqrt(N)] 的所有質數皆不整除 N，則 N 必為質數

 

作法：

(一)、建立 [1,1e5] 的質數表

(二)、根據引理一，輸入 N 之後拿 [1,sqrt(N)] 的質數試除

---------------------------------------------------------------------------------------

三、對測資二分搜 (Binary Search)

先備知識：二分搜尋法

 

如果輸入的數字 N 大於我們所預期的，那就讓程式 Runtime Error；如果輸入的數字 N 小於我們所預期的，那就讓程式 Time Limit Exceed。

根據上述的作法，便能一一抓出測試資料了，令人訝異的，我們只需要進行 31 次上述的操作，就一定能找到一行測試資料！

若是你會撰寫網路爬蟲，可以使用爬蟲慢慢把測試資料爬出來；如果你不會的話也沒關係，慢慢手動找，也能找出所有資料的。

 

額外知識：整體二分搜

如果你會整體二分，你可以對整組測試資料整體二分，有助於提升找測資的效能。

---------------------------------------------------------------------------------------

四、打表建表 (Sieve of Eratosthenes)

先備知識：Sieve of Eratosthenes

 

同方法二，打表建表的時，只要跳過 (2,3,5) 這三個質數，通常執行效率就夠快了。

---------------------------------------------------------------------------------------

五、編譯器建表 (Compiler Sieve)

先備知識：constexpr syntax

 

同方法二，只不過這次是用編譯器來建立質數表，藉此獲得更短的執行時間，不過相對的，伺服器會需要相當久(甚至比執行時間還久)的編譯時間。

---------------------------------------------------------------------------------------

六、本機建表 (Local Sieve)

先備知識：使用程式生成程式碼、壓縮程式碼、宣告極大陣列

同方法二，只不過這次是在本機先建立質數表，再把質數表寫入你的 Submission。

這樣的好處是不需要浪費時間在執行上，也不需要浪費時間在編譯上，十分的優秀。

---------------------------------------------------------------------------------------

七、究極解法 (Ultimate Solution)

先備知識：一個熱忱的心

 

我們都知道，輸入的數字 N 是有範圍的。

只要在本機計算出每一種輸入的回答，再將每個回答寫入程式碼，便能做到 O(1) 回答題目了！

這樣不只能夠 AC 這題，還能夠成為 Ranklist 上第一名！！！

---------------------------------------------------------------------------------------

很顯然這題目一點都不毒瘤，現在大家都會了嗎？

大家加油，努力一下就能把這題寫掉了，祝大家都能過這一題 ><

 

 

---

推一下，沉下去每次都找好久

 

---

再推(助攻手)  :)