主题质数及其应用.ppt

主題: 質數與其應用 解題技巧 如何判斷質數 建造質數表 類題討論 (含因數分解) 例題講解: A.10622 歷年題目 質數的定義 一個大於等於 2 的數，除了 1 及本身，沒有其他因數，就是質數 1 是不是質數依題目規定 (正確而言，不是) 今天討論假設: 無需處理「大數」 如何判斷質數 只要 2 到 n - 1 間的整數都不是 n 的因數，則 n 是質數 只要 2 到 sqrt(n) 間的整數都不是 n 的因數，則 n 是質數 假設已建好一範圍在 2 到 n - 1 (n ? 3) 之間的質數表，存在陣列 prime 中 prime[i] 代表第 i+1 個質數 只要比 sqrt(n) 小的所有質數都不是 n 的因數，則 n 是質數 (n ? 3) 建造質數表 基本法 6N ? 1 法 Sieve 法（篩法） 假設我們要求出在 1 ~ range 的範圍內所有的質數 基本法 利用判斷質數的方法造表 6N ? 1 法 只有 6N ? 1 的數字才需要測試，其他都是 2 or 3 的倍數 Sieve 法 ( 篩法 ) 不使用除法的建表法 對於每個質數來說，它的倍數一定不是質數，所以建立一個大小是 range 的陣列 is_prime，每看到一個質數，就把它的所有倍數砍掉，剩下就是質數 優點：快速 缺點：範圍有限 (range 不可以太大) 類題 406, 686 Problem: 因數分解 解法: 先建質數表，從質數表的第一個質數往後看到超過 sqrt(num)為止，只要除的盡就不斷的除以該質數 建立一個 list array (plist) 代表質因數列表 建立一個 counter array (ppow) 來代表每個質數的次數 類題 516、583 60 = 2^2 ? 3^1 ? 5^1 Problem: 求因數的個數 解法: 先做因數分解，代入求因數個數的公式 類題 294 Problem: 約分 以 為例，直接將分母分子算出，再做除法，有可能 overflow 解法: 將所有質數代入約分，再把分子乘出 類題 369，530，160 Problem: Goldbach’s conjecture Goldbach 假說: 所有的偶數都是兩個質數相加的和 類題 543，686，10168，10311 Problem 10168: 給一個偶數 n，找四個質數 p1，p2，p3，p4，使得 n = p1 + p2 + p3 + p4 Problem: 孫子點兵 有一數除以 3 餘 2，除以 5 餘 3，除以 7 餘 2，這個數字是多少? 類題 498 進階中國餘式定理 x = (mod M) M = m[0] ? m[1] ? … ? m[num_inp - 1] M[i] = M / m[i] M’[i] ? M[i] ? 1 (mod m[i]) 例題講解: A.10622(http://acm.uva.es/p/v106/10622/html) 給一個 int 允許的數字 x，且該數字絕對值大於等於 2 找 p，p 必須是所有可能的 x = b^p 中，最大的一個，b，p 為整數 Sample input/output 資料結構 #define range 66000 //比 65536 大即可 int num 輸入的數字 int is_prime [range] 篩法建立的質數表 int num_pfact num 的質因數個數 int ppow[range] num 因數分解後，每個質因數的次方數 解法 建質數表 質因數分解 決定最大次方數 考慮 num 是負數的狀況 Program structure construct_is_prime(); //建質數表 while(1) { scanf(“%d”, num); if(num == 0) break; // input 結束 flag = 0; // 假設 num 為正 if(num 0) flag = 1; // num 為負，改變 flag factorial(num); //因數分解，只需記次方數 find_max_power(); if(flag == 1) num_is_minus(); output(); } // end of while 決定最大次方數 如何決定最大次方數? n = 129600 = 26 ? 34 ? 52 = (23 ? 32 ? 5)2 n 的次方數必是質因數次方數的公因數 最大次方數為所有的質因數次方數求最大公因數 求公因數 a, b 兩數求公因數 輾轉相除法 若 num 是負的 只有奇數次方才有可能為負