質數 - HackMD

<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Prime ## 質數 10/13 preTrain --- ## 目標 : 質數判斷給定一個數 $N$，請問 $N$ 是否為質數? ---- - $\sqrt{N}$ 窮舉 - 暴力窮舉法 - $\sqrt{N}$ 優化 - 質數篩法 - 埃氏篩法 - 優化 - 質數篩法應用 : 質因數分解 - 方法一 - 方法二 --- ## $\sqrt{N}$ 窮舉 ---- ## 暴力窮舉法已知每個質因數都小於 $N$ 窮舉每個 $[2, N - 1]$ 的數字 $x$，判斷該數字是否整除 $N$ - if 存在 $x$，使 $n$ 整除 $x$，則 $n$ 是因數 - else $x$ 是質數 ---- 簡單的快速判斷，暴力跑過每個數字 ```cpp int n; cin >> n; for(int i = 2; i < n; i++){ if(n % i == 0){ //若整除則此數字絕對不是質數 cout << "NO\n"; break; //跳出迴圈 } if(i == n - 1){ //若到 n - 1 (也就是迴圈的最後一次) 都沒有跑出去代表他是質數 cout << "YES\n"; break; //跳出迴圈 } } ``` ---- ## 最差情況最差情況 : 判斷的數字是質數，因此要跑 $2\sim N-1$ 總共 $N-2$ 個數字 (除了 $1$ 跟 $N$) $\Rightarrow O(N)$ 以 $7$ 為例，我們要跑一個迴圈從 $2$ 跑到 $6$ 並且用每個數字去除除看 ---- ## $\sqrt{N}$ 優化由於因數性質的關係，所以對於一個數字的檢查，其實只需要從 $2$ 跑到 $\sqrt{N}$ 即可所以只需要檢查區間 $[2,\sqrt{N}]$ 的數字就好 ---- 稍微沒那麼暴力地判斷 $n$ 是否為質數 ```cpp= bool isPrime(int n){ bool ret = true; for(int i = 2; i * i <= n; i++){ // 檢查範圍只需要到根號 n if(n % i == 0){ // 若整除則此數字絕對不是質數 ret = false; break; } } return ret; } ``` ---- ## 小技巧在迴圈內請用 $i\times i \le n$ 而非 $i < \sqrt{n}+1$ 電腦中的 $\sqrt{n}$ 容易有浮點數誤差 ---- ## 時間複雜度分析針對一個數字詢問是否為質數，需要跑 $2$ 直到 $\sqrt n$ 因此時間複雜度為 $O(\sqrt n)$ --- 倘若今天有 $Q$ 筆詢問呢? 如果使用的是剛剛的方式，會變成 $Q \cdot \sqrt{N}$ $\Rightarrow$ Time Limit Exceed  ---- ## 質數篩法 ### Sieve of Eratosthenes ---- ## 想法觀察 : 最小的質數 $2$ 開始，所有質數的倍數都一定不是質數 $\Rightarrow$ 建立 **"$0/1$質數表"**，將質數的倍數都登記為 $0$ ---- ## 想法 ![](https://i.imgur.com/wZuoyk4.gif) ---- ## 演算法步驟從 $2$ 開始跑到 $N$，判斷當前數字是不是質數 (是否被更改過) - 如果是質數 (尚未被更改過)，把所有質數的倍數設成非質數 (更改) - 否則略過 ---- ## 核心程式碼 ```cpp= // n 為會跑到的最大值 bool notprime[1000005]; // 紀錄每個數字是否是質數 vector<int> prime; // 儲存範圍內所有的質數 notprime[1] = 1; // 1 代表此數字不是質數，否則為 0 // 先將所有大於 1 數字設為質數 (0) for(int i = 2; i <= n; i++){ // 根號 n 優化，篩到這就夠了! if(!notprime[i]){ // 如果為質數 prime.push_back(i); for(long long j = 2; i * j <= n; j++){ // 記得容易會爆 int 的話要設 long long notprime[i * j] = 1; // 所有質數的倍數設成非質數 } } } ``` ---- ## 時間複雜度  次數為 $\frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n}$ 為調和級數 $\approx n \log n$ $\Rightarrow$ 時間複雜度為 $O(n \log n)$ ---- ## 質數篩優化在內迴圈裡的倍數可以直接從 $i$ 倍開始，因為小於 $i$ 的倍數之前都跑過了 ```cpp= vector<int> prime; void sieve(){ for(int i = 2; i <= n; i++){ if(!notprime[i]){ prime.push_back(i); for(long long j = i; i * j <= n; j++){ // 這裡的 j 可以直接從 i 開始 notprime[j * i] = 1; } } } } ``` ---- ## 時間複雜度分析 $(\frac{N}{2} - 2) + (\frac{N}{3} - 3) + (\frac{N}{5} - 5) + ... + (\frac{N}{\sqrt{N}} - \sqrt{N})$ 複雜度為 $O(N\log\log N)$ ---- ## 小提醒記得 `j` 需使用 `long long` 型態，因 `i * i` 可能會到 `long long` 範圍($\ge 2\times 10^9$) --- ## 質數篩的應用對於這段程式 ```cpp= vector<int> prime; bool notprime[N]; void sieve(){ for(int i = 2; i <= n;i++){ if(!notprime[i]){ prime.push_back(i); for(long long j = i; i * j <= n; j++){ notprime[i * j] = 1; // 這裡改成 notprime[i * j] = i; } } } } ``` 若我們把第 $8$ 行的替代的元素換成 $i$ 是什麼意思呢? `notprime[i]` 若等於 $0$ 代表他是質數，不等於 $0$ 則代表其不是質數，且 `notprime[i]` 為 $i$ 的「質因數」。 ---- 對於每個質數 $i$ ，設值所有 i 的倍數的 factor 為 i (需注意 j 的起始值) ```cpp= void sieve(){ for(int i = 2; i <= n; i++){ if(!factor[i]){ prime.push_back(i); for(long long j = i; j <= n; j += i){ // 喔然後這行這樣寫也可以 :) factor[j] = i; // 紀錄當前數字i遇到的因數 } } } } ``` ---- 如果我們建好質數表，如果有多筆詢問每次只要查質數表，就可以直接判斷是不是質數 yeah :bread: ---- ## 質因數分解那我們有質數表之後，除了判斷一個數字是否為質數外，還可以用來質因數分解。 ---- 在質數表內 $factor[i]$ 的值為 $i$ 的其中一個質因數那我們在質因數分解 $n$ 的時候，只需要不斷除以 $factor[n]$ ，並且把中途的數字記錄下來即可 ---- ## 程式碼實現 (方法一) ```cpp void factorize(int x) { // 需要質因數分解的數字 vector<int> factors; while (x != 1) { factors.push_back(factor[x]); // 記錄所有因數 x /= factor[x]; // 把他除以自己的因數 } for (int i = 0; i < factors.size(); i++) { // 最後factors 就是質因數分解的結果 cout << factors[i] << " "; } } ``` ---- 如果要質因數分解的數字太大? 建表不夠大怎麼辦? 由小到大枚舉質數表內的質數，過程中判斷當前質數是否 $\le\sqrt{n}$，整除時代表此數字為因數，把此數字記錄下來並除掉  ---- ## 程式碼實現 ```cpp void factorize(int x) { vector<int> factors; // 質因數分解的答案存在這 // for 迴圈判斷當前遍歷到的質數還在範圍裡 for (int i = 0; i < primeSize && prime[i] * prime[i] <= x; i++) { while (x % prime[i] == 0) // 若當前枚舉到的質數是此數的因數 factors.push_back(prime[i]), x /= prime[i]; // 紀錄答案並更新 x } // 最後記得把自己加進去，若他本身是很大的質數則有可能沒算到 if (x > 1) factors.push_back(x); for (int i = 0; i < factors.size(); i++) // 遍歷並輸出答案 cout << factors[i] << " "; } ``` ---- ## 兩種質因數分解分析 - 範圍問題 - 第一種方法: 由於會戳到 $factor[x]$ ，因此 $x$ 的範圍需小於質數表大小 - 第二種方法: 能分解的範圍到 $prime[i]\times prime[i]$，因此值域上可以處理到 $N\times N$ ($N$為質數表的範圍) - 時間複雜度分析 - 第一種方法: 複雜度由質因數數量決定，最差的情況是所有質因數都是 $2$ (最小的質因數)，因此時間複雜度為 $O(\log x)$ - 第二種方法: $O(\sqrt x)$ 針對以上兩種分析就可以看出這兩種方法的優劣以及該如何選擇 ---- 之後會上到更快搜尋質數的方法能處理更大範圍 ($10^{18}$) 的質數問題 miller-rabin 有興趣再自己去看 ---- ## 補充一個數字 $n$ 的因數的數量最多只有 $n^{\frac{1}{3}}$ 個當題目需要枚舉因數時，如果要判斷因數數量有多少，可以用 $n^{\frac{1}{3}}$ 當成上界來分析複雜度。 --- ### 先下課休息 ### 等等還有另一個主題