主题：质数与其应用

主题：质数与其应用内容摘要：

表  建立一個 counter array (ppow) 來代表每個質數的次數  類題  51 583 14 2 3 5 2 1 1 60 plist ppow  60 = 2^2  3^1  5^1 15 memset(ppow, 0, sizeof(ppow))。 num_pfac = 0。 //質因數的個數 for(i = 2。 i = (int)sqrt(num)。 i++) { if(is_prime[i] == 0 amp。 amp。 num%i == 0) { //使用篩法的質數表 plist[num_pfac] = i。 // 放入質因數列表 while(num%i == 0) { ppow[num_pfac]++。 //更新次數列表 num = num/i。 } num_pfac++。 } } if(num_pfac == 0) { // 質數表中找不到因數 : 自己就是質數 plist[0] = num。 ppow[0] = 1。 num_pfac = 1。 } 16 Problem: 求因數的個數  解法 : 先做因數分解，代入求因數個數的公式  類題  294 mqmqq pppn  ...2121(q1+1)  (q2+1)  …  (qm+1) 因數個數 17 Problem: 約分  以 為例，直接將分母分子算出，再做除法，有可能 overflow  解法 : 將所有質數代入約分，再把分子乘出  類題  369， 530， 160 nmC4201743537495123478910104 C18 Problem: Goldbach’s conjecture  Goldbach 假說 : 所有的偶數都是兩個質數相加的和  類題  543， 686， 10168， 10311  Problem 10168:  給一個偶數 n，找四個質數 p1， p2， p3， p4，使得 n = p1 + p2 + p3 +。