質數(prime)

何謂質數? 所謂的質數就是指一正整數 除了1和自己本身以外沒有其他因數 而此正整數就稱為質數。

怎麼檢查一個正整數 是否為質數呢?

將正整數除以比它小的所有正整數 ex: 97 97%2=1 97%3=1 97%4=1 97%5=2 97%6=1 97%7=6 97%8=1 97%9=7 97%10=7 97%11=9 97%12=1 97%13=6 97%14=13 97%15=7 97%16=1 97%17=12 97%18=7 97%19=2 97%20=17 97%21=13 97%22=9 97%23=5 97%24=1 97%25=22 97%26=19 97%27=16 97%28=13 97%29=10 97%30=7 97%31=4 97%32=1 97%33=31 97%34=29 97%35=27 97%36=25 97%37=23 97%38=21 97%39=19 97%40=17 97%41=15 97%42=13 97%43=11 97%44=9 97%45=7 97%46=5 97%47=3 97%48=1 97%49=48 97%50=47 97%51=46 97%52=45 97%53=44 97%54=43 97%55=42 97%56=41 97%57=40 97%58=39 97%59=38 97%60=37 97%61=36 97%62=35 97%63=34 97%64=33 97%65=32 97%66=31 97%67=30 97%68=29 97%69=28 97%70=27 97%71=26 97%72=25 97%73=24 97%74=23 97%75=22 97%76=21 97%77=20 97%78=19 97%79=18 97%80=17 97%81=16 97%82=15 97%83=14 97%84=13 97%85=12 97%86=11 97%87=10 97%88=9 97%89=8 97%90=7 97%91=6 97%92=5 97%93=4 97%94=3 97%95=2 97%96=1

高中教過的質數檢查法 根據高中學過的因數成對定理 檢查2～N1/2 ，看看是否有N的因數 ex: 97 97%2=1 97%3=1 97%4=1 97%5=2 97%6=1 97%7=6 97%8=1 97%9=7

檢查2~N1/2奇數 偶數一定是2的倍數 97%2=1 97%3=1 97%5=2 97%7=6 97%9=7

如果要找好幾個質數， 上面的方法就很慢， 因為每找一個質數就要從頭跑一次

篩法 利用一條bool array來紀錄他是不是質數 1 2 3 4 5 6 7 8 9 10 11 T 1 2 3 4 5 6 7 8 9 2.將0和1改為F(非質數)，再往下尋找質數。 3.當找到一個質數後，將此質數的倍數歸F為非質數。 4.往下尋找質數，重複步驟3.直到尋找到的質數大於√N為止。 結論： 雖然篩法的程式寫起來很簡單，不過缺點是很占記憶體空間。 1 2 3 4 5 6 7 8 9 10 11 T 1 2 3 4 5 6 7 8 9 10 11 F F F F F F F T：質數 F：非質數 i = 2 3

跳二跳四法 × 什麼是跳二跳四？我們就先拿６來區分一下正整數: (2和3例外) 6n 6n+1 6n+2 6n+3 6n+4 6n+5 6.12.18 .24….. 1.7.13. 19.25 8.14. 20….. 9.15. 21…. 4.10.16. .22….. 5.11.17. .23.29. 6的倍數 × 需檢查 Ex.25 2的倍數 3的倍數 Ex.35

跳二跳四法 我們知道以６來區分的正整數中，只有(6n+1)和(6n+5)比較有可能會有質數出現：

1 2 2 4 2 4 2 4 6 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 25 2 4 2 6 4 2 4 6 6 2 35 49 55 4 2 2 4 2 4 6 4 2 6 4 6 8 91 65 77 85 2 2 4 95 4 4 2 2 2 4

因此… -開一條名為prime的int array -在0和1的位置放入2、3兩數 -設一個target變數，從5開始檢查 它存於prime的array中。 （檢查小於等於target開根號的質數 是否能整除它即可。） -將target加2 -將target加4

target= 7 29 5 23 31 25 11 19 13 17 +2 +4 1 2 3 4 5 6 7 8 9 10 2 3 5 5 7 11 13 17 19 23 29 31

我們所需要的質數表到底要 開多大呢？

質數表大小 依照因數成對定理， 我們可以知道一個正整數， 只要不被自己的平方根以下的正整數整除就是質數， 由上述之方法可以知道一件事， 就是質數表至少需要開到質數數字小於等於√N的大小， 此外還要另外再開一個空間來存大於√N的質數。

5 3 target= 13 39 prime[i]= 3 2 target%prime[i]= 1 1 EX ：39 NULL (39)1/2 ≒ 6.2 EX ：39 target= 13 39 /prime[1] i = 1 i = 0 i = 3 i = 2 prime[i]= NULL 5 3 2 target%prime[i]= 3 1 1 大於√N的質因數 1 2 NULL NULL 13 質數表 1 2 3 5 次方表 1 2 1

練習題 543 Goldbach’s Conjecture 406 Prime Cuts 10924 Prime Words 10235 Simply Emirp 543 Goldbach’s Conjecture

質因數分解 何謂質因數分解？ 就是把各數中相同的質因數提出來後再相乘。

質因數分解 -建立質數表 -開一條一樣長的array -做質因數分解，把對應的因次存入 1 2 3 4 5 6 7 8 9 10 11 13 EX ：100 1 2 3 4 5 6 7 8 9 10 11 13 17 19 23 29 31 1 2 3 4 5 6 7 8 9 10

質因數分解的建表 target= 33 99 1 11 prime[i]= 2 11 3 5 3 7 target%prime[i]= 2 2 1 1 4 1 2 3 4 5 6 7 8 9 10 11 13 17 19 23 29 31 1 2 3 4 5 6 7 8 9 10 2 1 1

階乘的質因數分解 可能會有人想說直接乘開後再質因數分解， 可是這方法是絕對不行的， 因為當數字到達20!時， 就會超過int的範圍造成overflow的問題。

階乘的質因數分解(原理) 2的因式 Ex.10! = number 1.將兩兩分成一組：(有2的因式就除2，寫下商) number = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 number = 1 2 3 4 5 =>25 2.再將兩兩分成一組：(有2的因式就再除2，寫下商) number = 1 * 2 * 3 * 4 * 5 number = 1 2 =>22 3.再將兩兩分成一組：(有2的因式就再除2，寫下商) number = 1 * 2 number = 1 =>21 所以，共有28

階乘的質因數分解(原理) 3的因式 4. 接下來的3是將三個一組： number = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 number = 1 2 3 =>33 5.三個一組，再除一次3： number = 1 * 2 * 3 number = 1 =>31 所以，共有34

階乘的質因數分解(原理) 10! = 28 * 34 * 52 * 71 5的因式 6. 接下來的5是將五個一組： number = 1* 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 number = 1 2 =>52 所以，共有52 7的因式 7. 接下來的7是將七個一組： number = 1 =>71 所以，共有71 10! = 28 * 34 * 52 * 71

階乘的質因數分解(原理) 8.其實這道理很簡單，若除數2，表示從1開始每兩相鄰數中，一定會有一個數字是二的倍數，所以1~10裡有一定5個數為2的倍數，再將這5個數看成一組，此5個數裡一定會再有 2個數為2的倍數，又將此2個數看成一組，必定有1個數為2的倍數  可知 10! 裡共有8個2。 9.根據這原則，找出1~10共有幾個3、5、7，找出來的數就是此質因數的次方。

Ex. 10! 先設一變數為level，且level = 10。 再設一個變數 temp = level (目的是在過程中不要 一樣設一個 int 陣列與 prime 同長度，名為 factor，且初始值皆歸零。 質因數分解是每遇到整除才把factor [i] ++，而 temp才會換成商。但在階乘的質因數分解法裡 不管有沒有整除都把商加到factor [i]，而temp 一樣是換成商，反覆做直到temp = 0， 再將i ++ 往下個質數繼續分解，但須重新再將level值存入 temp，即 temp = level，然後再對此質數做一 樣的動作，直到小於level的質數皆完成上述動 作為止。

level = 10 temp = 1 1 10 2 1 2 5 3 i = 3 4 2 1 prime [i] = 11 7 5 3 2 10! = 28 * 34 * 52 * 71 temp / prime [i] = 2 2 1 3 1 1 5 factor [i] = factor [i] + (temp / prime [i]) = + = 3 7 5 1 1 3 2 1 2 5 8 7 1 5 2 4 3 prime 1 2 3 4 5 6 7 8 9 11 13 17 19 23 29 factor 1 2 3 4 5 6 7 8 9 5 7 8 3 4 2 1

練習題 質因數分解 516 Prime Land 583 Prime Factors 階乘的質因數分解 10139 Factovisors