首先試除幾乎一定會爆，理由：
複雜度是O(sqrt(n))，常數壓再低這裡n有大概2e9，測資數量2e5
粗略估一下 要1e9以上的步驟
建表，假使是用sieve method，開的表大小O(n)，時間線性
這樣就算記憶體夠用時間還是會爆，其他諸如建一半的表那通常還是會爆
因為最糟複雜度沒辦法壓到sqrt(n)以下。
我所採用的對應方法是Miller Rabin，有個定理告訴我們對任何質數p，令p-1 = 2^r * d
那麼對所有 a in [1,p-1]，下面兩個條件一個會成立
a^(d) 同餘 1 (mod n)
or
a^(2^s * d) 同餘 -1, for some s
拿這個去檢驗質數非常高效，複雜度是對數量級的。
值得注意的是，質數一定會通過檢驗，但合數有可能也會通過檢驗，
只是在諸如int 或 long long int範圍內已經有人找到一些對應的完全有效的a可以拿來用。
有興趣的人不妨查一下Miller Rabin這個算法。
建一半的表那通常還是會爆
因為最糟複雜度沒辦法壓到sqrt(n)以下。
啊，這裡修正一下
建sqrt(n)的表，單筆測資的最糟複雜度是sqrt(phi(n))
因為phi(n)和n其實滿接近的
建表仍然很有可能會爆掉(可能可以壓線過但很勉強
((考慮一種情況是每筆測資都出超大質數
首先試除幾乎一定會爆，理由：
複雜度是O(sqrt(n))，常數壓再低這裡n有大概2e9，測資數量2e5
粗略估一下 要1e9以上的步驟
建表，假使是用sieve method，開的表大小O(n)，時間線性
這樣就算記憶體夠用時間還是會爆，其他諸如建一半的表那通常還是會爆
因為最糟複雜度沒辦法壓到sqrt(n)以下。
我所採用的對應方法是Miller Rabin，有個定理告訴我們對任何質數p，令p-1 = 2^r * d
那麼對所有 a in [1,p-1]，下面兩個條件一個會成立
a^(d) 同餘 1 (mod n)
or
a^(2^s * d) 同餘 -1, for some s
拿這個去檢驗質數非常高效，複雜度是對數量級的。
值得注意的是，質數一定會通過檢驗，但合數有可能也會通過檢驗，
只是在諸如int 或 long long int範圍內已經有人找到一些對應的完全有效的a可以拿來用。
有興趣的人不妨查一下Miller Rabin這個算法。