MediumRating 1737
3044. Most Frequent Prime
arrayhash-tablemathmatrixcountingenumerationnumber-theory
解題說明
Most Frequent Prime
題目描述：給定一個 m×n 的矩陣，從每個格子出發，沿八個方向（上、下、左、右、四個對角線）行進，將經過的數字依序串接形成數值。找出所有大於 10 的質數中出現頻率最高的那個。若有多個頻率相同則回傳最大值，若無質數則回傳 -1。
解題思路：由於矩陣最大只有 6×6，每個方向最多 6 步，生成的數字數量有限。對每個格子、每個方向枚舉所有可能的串接數字，用質數判定函數檢查是否為質數，再用雜湊表統計頻率。最後找出頻率最高且值最大的質數。質數判定對每個數字使用試除法到 sqrt(n)。
C++ 解法
複雜度分析
時間複雜度：O(m × n × 8 × D × sqrt(V)) — 其中 D 為矩陣最大維度（最多 6），V 為生成數值的上界（最多 6 位數），sqrt(V) 為質數判定成本。整體為常數級別。
空間複雜度：O(K) — K 為不同質數數量，存於雜湊表中。
虛擬碼
1. For each cell (i, j) in matrix:
2. For each of 8 directions (dx, dy):
a. Start with num = mat[i][j]
b. Move to (x, y) = (i+dx, j+dy)
c. While in bounds: num = num*10 + mat[x][y]
d. If num is prime (> 10), increment freq[num]
e. Continue moving in same direction
3. Find the prime with highest frequency (break ties by largest value)
4. Return that prime, or -1 if no primes found其他解法
埃拉托斯特尼篩法預處理：由於生成的數字最大為 6 位數（999999），可預先用篩法建立質數表，將質數判定從 O(sqrt(V)) 降為 O(1) 查表。在矩陣較大或多次查詢時更有效率。
只枚舉長度 >= 2 的路徑：題目要求大於 10，因此單一格子的數字不需要檢查，可在內層迴圈開始時就跳過第一步。
延伸思考
- 如果矩陣大小增加到 100×100，生成的數字可能非常大，該如何處理大數質數判定？
- 如果允許路徑轉彎（不限直線），問題的複雜度會如何變化？
- 如果要找出現頻率前 K 高的質數，該如何修改演算法？