主題

ZeroJudge - e684: 00897 - Anagrammatic Primes　解題心得

Not In My Back Yard | 2020-02-26 01:03:23 | 巴幣 0 | 人氣 165

題目連結：

e684: 00897 - Anagrammatic Primes

題目大意：

輸入有多列，每列給定一正整數 n （n ＜ 10000000，n ＝ 0 時代表輸入結束），請找到一正整數比 n 大而且盡可能地接近 n 並且跟 n 一樣長，滿足將該數之各個位數任意排列重組必定得一質數。

例如 919 重新排列可得 199 、 919 、 991 ，此三數皆為質數。

如果找不到這種數，請輸出「0」。

範例輸入：

10

16

900

113

8000000

0

範例輸出：

11

17

919

131

0

解題思維：

如果有自己暴力硬 A 過的話，會發現這樣子的數相當地罕見。

小於 10000000 的這樣子的數（其被命名為「可交換質數」（Permutable Prime））只有 22 個。分別是 2 、 3 、 5 、 7 、 11 、 13 、 17 、 31 、 37 、 71 、 73 、 79 、 97 、 113 、 131 、 199 、 311 、 337 、373 、 733 、 919 、 991 。而且有一些數互相是彼此的排列組合之一。

因此，就從這 22 個數字去判斷是否與條件相符。符合就輸出該數字；反之，則輸出「0」。

本人的程式碼（於 CodePile 上）

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

#程式題目解題心得