16.4 根號複雜度：質數判斷

本站題目〈質數判斷〉：Q \le 100 筆詢問，每筆給一個不超過 10^{11} 的正整數，判斷是不是質數。

上冊 4.5 的做法是拿 2 到 n-1 逐一試除——O(n)。這裡 n 到 10^{11}，單筆詢問就要一百秒，連一筆都跑不完。

換形狀的鑰匙在 10.1 就鋪過：因數成對出現。36 = 2 \times 18 = 3 \times 12 = 4 \times 9 = 6 \times 6，每一對裡總有一個不超過 \sqrt{36} = 6——所以試到 \sqrt{n} 都沒找到因數，就能斷定 n 是質數。試除範圍從 n 砍到 \sqrt{n}，10^{11} 變成約 3.2 \times 10^5。