目錄

一、什么是質數

二、如何判斷質數

1.樸素法（暴力枚舉）

2.優化

三、分解質因數

四、質數篩法

1.樸素篩法

2. 埃式篩法

3.線性篩?

五、試除法求解約數

六、約數的個數以及約數之和

七、歐幾里得算法（輾轉相除法）

總結

---

一、什么是質數

????????質數是指在大于1的自然數中，除了1和它本身以外不再有其他因數的自然數。

? ? ? ? 算數基本定理，也叫唯一分解定理。任何一個大于1的自然數?N,如果N不為質數，那么N可以唯一分解成有限個質數的乘積N=P1a1P2a2P3a3......Pnan，這里P1<P2<P3......<Pn均為z質數，其中指數ai是正整數。

二、如何判斷質數

1.樸素法（暴力枚舉）

? ? ? ? 暴力遍歷[2,x）之間的所有數字，判斷能否整除， 時間復雜度O(n)

bool is_prime(int x) {if (x < 2) return false;for (int i = 2; i < x; i++) {if (x % i == 0) return false;}return true; }

2.優化

? ? ? ? 對于一個整數n, 如果n整除p， 那么n也整除 n /p， 因此可以將枚舉的范圍從[0, n]降到[0,?];時間復雜度O()

bool is_prime(int x) {if (x < 2) return false;for (int i = 2; i <= x / i; i++) {if (x % i == 0) return false;}return true; }

三、分解質因數

? ? ? ? 問題：獲取給定的數字n的所有質因數以及質因數的數量；即分解定理中的p和正整數a

void divide(int x) { for (int i = 2; i <= x; i++) {if (x % i == 0) { // i一定是一個質數int res = 0;while (x % i == 0) {x /= i;res ++;}cout << i << " " << res << endl;}}cout << endl; }

? ? ? ? 對于 x % i == 0此時的i一定是質數；當處理這段話的時候，x此時一定處理了[2, i - 1]之間的所有質數，即當前x不能被[2, i - 1]中的質數整除；假設i不是質數，那么肯定[2, i - 1]中的某個質數，假設不成立；所以此時 i 一定是一個質數? ? ? ??

????????時間復雜度O(n)

- 如何優化？考慮將范圍降到[2,?],? 更改循環條件： i <= x / i

????????存在結論：至少存在一個質數i >=??; 假設存在兩個大于?的質數的情況，那么這兩個數的乘積一定大于n，假設不成立。

void divide(int x) { // logn ~ 根號n之間的時間復雜度for (int i = 2; i <= x / i; i++) {if (x % i == 0) { // i一定是一個質數int res = 0;while (x % i == 0) {x /= i;res ++;}cout << i << " " << res << endl;}}if (x > 1) cout << x << " 1" << endl; cout << endl; }

? ? ? ? 時間復雜度O(), 但是實際上時間復雜度并不會這么高，如果n是2的整數次冪，那么在2的時候n就可以被整除，所以時間復雜度降為O(logn)；因此實現的時候，只需要在最后額外判斷一次就可以

四、質數篩法

1.樸素篩法

? ? ? ? 循環[2, n], 每次將i的整數倍直接篩掉

void attainPrime(int n) {// 樸素版for (int i = 2; i <= n; i++) {if (!vis[i]) primes[res ++] = i; // primes用來記錄質數// 刪掉i的倍數for (int j = i + i; j <= n; j += i) vis[j] = true;} }

? ? ? ? 當時，篩選次數為, 調和級數發散，趨近于O(logn)

2. 埃式篩法

? ? ? ? 思想：相比于樸素篩，埃式篩法并不是篩掉所有[2, n]數字的倍數，而是僅僅篩掉質數的倍數

將2到n范圍內的所有整數寫下來。其中最小的數字2是素數。將表中所有2的倍數都劃去。表中剩余的最小數字是3，它不能被更小的數整除，所以是素數。再將表中所有3的倍數都劃去。依此類推

void attainPrime(int n) {// 埃式篩法for (int i = 2; i <= n; i++) {if (!vis[i]) {primes[res ++] = i;// 只刪除質數的倍數for (int j = i + i; j <= n; j += i) vis[j] = true;}} }

? ? ? ? 時間復雜度O(nlognlogn)

3.線性篩?

? ? ? ? 在埃式篩法的思想基礎上，每次只用最小質因子刪除，保證每個數只被刪除一次，這樣就將時間復雜度降到了O(n)

void attainPrime(int n) {// 埃式篩法for (int i = 2; i <= n; i++) {if (!vis[i]) {primes[res ++] = i;}// 用最小質因子篩for (int j = 0; primes[j] <= n / i; j++) {vis[primes[j] * i] = true;if (i % primes[j] == 0) break;}} }

算法正確性在于：i % primes[j] (后面使用pj）

? ? ? ? 由于pj是從小到大排序的，所以pj一定是當前數的最小質因子

五、試除法求解約數

? ? ? ? 如果 d | a， 那么 d / i | a， 因此可以縮小范圍

stack<int> st;for (int i = 1; i <= x / i; i++) {if (x % i == 0) {cout << i << " ";if (x / i != i) st.push(x / i);}}// i 是從小到大枚舉的，所以通過stack將 x / i 逆序while (st.size()) {cout << st.top() << " ";st.pop();}

六、約數的個數以及約數之和

? ? ? ? 約數個數：?根據唯一分解定理，每一個x都可以分解成質因子的整數次冪的乘積。相應的每一個質因子的整數次冪就是個數，乘積的約數個數就是（a1 + 1）* (a2 + 1) * ... * (an + 1)

LL res = 1;unordered_map<int, int> um;while (n --) {int x;cin >> x;for (int i = 2; i <= x / i; i++) {while (x % i == 0) {x /= i;um[i] ++;}}if (x > 1) um[x] ++;}for (auto m : um) {res = res * (m.second + 1) % MOD;}

? ? ? ? 約數之和：根據唯一分解定理，每一個x都可以分解成質因子的整數次冪的乘積。相應的每一個質因子的整數次冪就是個數，乘積的約數之和就是（a1^0 + a1 ^ 1 + ... + a1 ^ n）* （a2^0 + a2 ^ 1 + ... + a2 ^ n）* （an^0 + an ^ 1 + ... + an ^ n）

LL res = 1;unordered_map<int, int> um;while (n --) {int x;cin >> x;for (int i = 2; i <= x / i; i++) {while (x % i == 0) {x /= i;um[i] ++;}}if (x > 1) um[x] ++;}for (auto m : um) {int p = m.first, number = m.second;LL res1 = 1;while (number --) res1 = (p * res1 + 1) % MOD;res = res * res1 % MOD;}

七、歐幾里得算法（輾轉相除法）

? ? ? ? 關鍵公式：gcd(a, b) = gcd(b, a % b)

int gcd(int a, int b) {return b ? gcd(b, a % b) : a; }

總結

? ? ? ? emmm，簡單整理下質數的學習，判斷質數，分解質因子以及幾種篩法，數學證明自己也并沒完全掌握，希望在整理過程中能夠加深理解。書寫中還會存在不嚴謹的地方，還望指正。

? ? ? ? 描述的都是一些模板題，我還在初學當中

? ? ? ? 題目均來自Acwing官網，可以參考學習?AcWing一個專屬于程序員的平臺，為大家在漫漫的刷題之旅中，提供最優質的解答https://www.acwing.com/about/

總結

以上是生活随笔為你收集整理的数论入门学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。