其實在數字很大的時候，做排列+判斷質數會很慢

可以先自己多測幾組測資

就會發現，數字大於一定值的時候，就要輸出 0 

對於相關的知識可以 google "可交換質數"

這題我用 python 建表

建到 4 位數  17ms

建到 7 位數  0.2s

建到 8 位數  0.9s

建到 3 位數  17ms

其實 3 位後面就不用了 哈哈哈

因為題目有限制 n < 10000000

在範圍內最大就 3 位數，

下一個可交換質數 已大於題目範圍 是 1111111111111111111

所以 google 一下答案就出來囉～

雖然可以透過 google 找到可交換質數的數列，但我想這並非出題者的本意(?)

回到問題的原意是如何有效率地去檢驗 1e7 以內的可交換質數？

觀察『可交換質數』的定義可以發現：可交換質數除了２,５ 以外一定是由{１,３,７,９}的數字構成而且題目保證查詢的數字＜1e7

這句話的意思是我們需要處理的位數最多到６位。暴力法產生個數介於(1,6)的所有組合後檢驗該組合能產生所有排列的數字並逐一確認是否皆為質數。

這樣的做法需要的時間為 O(5^6) (每次可以從{×,１,３,７,９}挑個數字，×代表不選，最多挑滿６個)＋(最多)6個數字做排列後檢驗。

這種『非直覺』須透過觀察來實現的『暴力法』題目可以挑戰 c658小新的提款卡密碼。

看秒數就知道有沒有確實建表。

我是在本地端暴力完後生成 < 10000000 裡的可交換質數。

因為數量不多，所以就直接建表了XD