moea_joint_essay
113年
[統計資訊] 資料庫及資料探勘、程式設計
第 六 題
請使用程式語言設計 1 個低時間複雜度的函式，傳入 a、b 皆為不大於 2^30 的正整數後，可判斷出 |a - b| 的值是否只有 3 個因數，並註明所使用的程式語言。（20 分）
(註：該函式只允許呼叫平方根函式。)
(註：該函式只允許呼叫平方根函式。)
📝 此題為申論題
思路引導 VIP
數值只有「恰好 3 個因數」的充分必要條件是「該數為某個質數的平方」。因此先計算 |a - b|，判斷它是否為完全平方數，若是的話再對其平方根進行質數測試。時間複雜度降為 O(sqrt(sqrt(|a-b|)))。
🤖
AI 詳解
AI 專屬家教
所使用的程式語言：C++ 邏輯說明： 一個正整數若恰好只有 3 個因數，該數必然是「某個質數的平方」（其因數為 1、該質數、以及該數字本身）。
▼ 還有更多解析內容