moea_joint_essay
113年
[資訊] 資訊管理、程式設計
第 六 題
六、請使用程式語言設計 1 個低時間複雜度的函式，傳入 a、b 皆為不大於 2^30 的正整數後，可判斷出 |a - b| 的值是否只有 3 個因數，並註明所使用的程式語言。（20 分）
(註：該函式只允許呼叫平方根函式。)
(註：該函式只允許呼叫平方根函式。)
📝 此題為申論題
思路引導 VIP
數學上，一個正整數如果「恰好有 3 個因數」，它必定是「質數的平方」。因此先計算 |a - b|，判斷是否為完全平方數，再針對其平方根使用迴圈檢驗是否為質數即可達成極低的時間複雜度 O( (|a-b|)^(1/4) )。