數論——質數與約數

2022 年 1 月 18 日
筆記
數學知識

一、質數

【相關概念】

因數：一整數被另一整數整除,後者即是前者的因數,如1,2,4都為8的因數
倍數：一個數能夠被另一數整除，這個數就是另一數的倍數。如15能夠被3或5整除，因此15是3的倍數，也是5的倍數。
質數：一個數除了1和它本身沒有其他的因數，就叫質數。如2，3，5，7，
和數：一個數除了1和它本身還有其他的因數，（至少有3個因數）就叫合數。如4，6，8，9

1.質數的判斷

（1）質數的判斷——枚舉法

//根據質數定義判斷 一個數是否為質數 O(n)
bool is_prime(int n)  // 判定質數
{
    if(n < 2) return false;
    for (int i = 2; i < n; i ++ )
    {
        if(n % i == 0)
            return false;
    }

    return true;        
}

（2）質數的判斷——試除法

上述短除法是從頭到尾枚舉判斷，時間複雜度相對很高，其實沒有必要枚舉1~n所有的數然後判斷！

思路:

把1~根號n之間的數都找一遍，看看有沒有一個數是n的因子，之所以找到根號n，是因為因子都是成對出現的，假設i是n的因子，那麼在根號n後面必定有一個數n/i是n的因子。（只枚舉每一對因子中較小的數）。

i | n 那麼 n/i | n ，即枚舉i的範圍從2~n/i即可（只枚舉每一對因子中較小的數）

i*i <= n 所以 i <= sqrt(n)，即時間複雜度O(sqrt(n))

//試除法 判斷一個數是否為質數 O(sqrt(n))
bool is_prime(int n)  
{
    if(n < 2) return false;
    for (int i = 2; i <= n / i; i ++ )
    {
        if(n % i == 0)
            return false;
    }

    return true;        
}

2.分解質因數

【相關概念】

什麼是質因數？

如果一個數的因數是質數，那麼這因數就是質因數！

什麼是分解質因數？

把一個合數分解成若干個質因數的乘積的形式，即求質因數的過程叫做分解質因數。

（1）分解質因數——短除法

小學時分解質因數的方法——短除法

分解質因數只針對合數（質數就只有本身和1兩個因數，不能分解）。一個數分解質因數，要從最小的質數除起（依次除於質數2 3 5….），一直除到結果為質數為止。分解質因數的算式叫短除法.

【參考代碼】

短除法分解質因數——O(n)

void divide(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(n % i == 0)//i一定是質數
        {
            int s = 0;
            while(n % i == 0)//短除法分解質因數
            {
                n /= i;
                s ++;//統計i出現的次數
            }
            printf("%d %d\n", i, s);
        }
    }
}

（2）分解質因數——試除法

上述短除法分解質因數，要從最小的質數除起（依次除於質數2 3 5….)一直到n，時間複雜度為O(n)，其實也沒必要枚舉1~n所有質數然後進行判斷！

這裡有一個重要的性質

n中最多只含有一個大於sqrt(n)的質因子。

證明：通過反證法：如果有兩個大於sqrt(n)的因子，那麼相乘會大於n，矛盾。證畢

於是我們發現最多只有一個大於sqrt(n)的因子，對其進行優化。先考慮比sqrt(n)小的，代碼和質數的判定類似

最後如果n還是>1，說明此時的n就是大於sqrt(n)的唯一質因子，輸出即可。（特判）

【參考代碼】

試除法分解質因數——O(sqrt(n))

void divide(int n)
{
    for(int i = 2; i <= n / i; i ++)
    {
        if(n % i == 0)//i一定是質數
        {
            int s = 0;
            while(n % i == 0)//短除法分解質因數
            {
                n /= i;
                s ++;//統計i出現的次數(指數)
            }
            printf("%d %d\n", i, s);
        }
    }
    
    if(n > 1) printf("%d %d\n", n, 1);//當n沒有變化的時候，輸出本身和1
}

證明一下循環裏面的i一定是一個質數：假如 i 是一個合數，那麼它一定可以分解成多個質因子相乘的形式，這多個質因子同時也是 n 的質因子且比i要小，而比i小的數在之前的循環過程中一定是被條件除完了的，所以i不可能是合數，只可能是質數

3.篩質數

求某個數n有多少個質數？

1.樸素篩法

枚舉i：2~n，從前往後把每個數對應的倍數都刪除掉，這樣篩過之後，所有剩下的數都是質數。（每個數i不存在該數的約數）

時間複雜度：O(nlogn)

int prime[N], cnt;//prime數組存儲質數，cnt統計個數
bool st[N];//標記是否被篩過

//樸素篩法-O(nlogn)
void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])//如果沒被篩過
        {
            prime[cnt ++] = i;
        }
        //把i的每一個倍數結果刪掉
        for(int j = i + i; j <= n; j += i) st[j] = true;
    }
}

2.埃氏篩法

埃氏篩法是對樸素篩法的一種優化方式，我們並不需要把2~n的每一個數的倍數都刪掉，可以只把所有質數的倍數刪掉！

埃氏篩法：我們會發現4的倍數也是2的倍數，所有我們只需要把所有質數的倍數刪除就好。
時間複雜度：O(n * loglogn)，近似O(n)

//樸素篩法-O(n * loglogn)
void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])//如果沒被篩過
        {
            prime[cnt ++] = i;
            //把質數i的每一個倍數結果刪掉
        	for(int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}

3.線性（歐拉）篩法

埃氏篩法的缺陷：對於一個合數，有可能被篩多次。例如 30 = 2 * 15 = 3 * 10 = 5*6……那麼如何確保每個合數只被篩選一次呢？我們只要用它的最小質因子來篩選即可，這便是歐拉篩法。

歐拉篩法的基本思想 ：在埃氏篩法的基礎上，讓每個合數只被它的最小質因子篩選一次，以達到不重複的目的。

int prime[N], cnt;
bool st[N];

// 合數 = 質數（最小） x 因數
//線性篩法-O(n)
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        // 如果沒被篩過 將素數記下來
        if(!st[i]) prime[cnt ++] = i;
        // 從小到大枚舉所有質數
        for(int j = 0; i * prime[j] <= n; j ++)//primes[j]*i<=n,把大於n的合數都篩了就沒啥意義了
        {
            // 每個合數只被它的最小質因子篩掉
            st[i * prime[j]] = true;
            
            if(i % prime[j] == 0) break;// prime[j]一定是(合數)i的最小質因子（從小到大枚舉質數嘛） 
        }
    }
}

i % prime[j] == 0

prime[j]一定是(合數)i的最小質因子，prime[j]也一定是prime[j] * i的最小質因子

i % prime[j] != 0

沒有找到i的任何一個質因子，說明當前prime[j]一定小於i的所有質因子（質數是從小到大枚舉的），prime[j]也一定是prime[j] * i的最小質因子

任何一個合數一定會被篩掉：

對於任何一個合數，它都會有且只有一個最小的質因子！因此只會被篩一次！

對比

二、約數

約束定義：

約數又稱因數，整數A除以整數B(B≠0) 除得的商正好是整數而沒有餘數，我們就說A能被B整除，或B能整除A。A稱為B的倍數，B稱為A的約數。

質數只有兩個約數：1和它本身。

合數至少有3個約數。

1.試除法求約數

思路：

O(sqrt(n))的做法，枚舉一個較小的因子，另一個直接用原數去除。

注意完全平方數只要加入一個因子。

一個數d要是能被n整除，那麼n/d也能被n整除，即約數也是成對存在的，我們只需枚舉較小的約數即可，另一個通過 n / d求出！從1枚舉到sqrt(n)即可，即i <= n /i。

註：

當n為完全平方數時，約數只存儲一次，不能夠重複存儲！因此要注意特判！

【代碼實現】

vector<int> get_divisor(int n)
{
    vector<int> res;
    
    for(int i = 1; i <= n / i; i ++)
    {
        if(n % i == 0)
        {
            res.push_back(i);
            if(i != n / i) res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

【acwing 869 試除法求約數】

給定 nn 個正整數 aiai，對於每個整數 aiai，請你按照從小到大的順序輸出它的所有約數。

輸入格式

第一行包含整數 nn。

接下來 nn 行，每行包含一個整數 aiai。

輸出格式

輸出共 nn 行，其中第 ii 行輸出第 ii 個整數 aiai 的所有約數。

數據範圍

1≤n≤1001≤n≤100,
2≤ai≤2×1092≤ai≤2×109

輸入樣例：
2
6
8
輸出樣例：
1 2 3 6 
1 2 4 8 

【代碼實現】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> get_divisor(int n)
{
    vector<int> res;
    
    //將成對的約數存下來，平方數只存一次
    for(int i = 1; i <= n / i; i ++)
    {
        if(n % i == 0)
        {
            res.push_back(i);//較小的約數
            //特判 防止重複存儲n為平方數的情況 
            if(i != n / i) res.push_back(n / i);//存另一個約數 較大的約數
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
        int a;
        scanf("%d", &a);
        
        auto res = get_divisor(a);
        for(auto c : res) cout << c << " ";
        puts("");
    }
    
    return 0;
}

for(auto x : arr) 遍歷方式， x只是將arr里的元素複製下來，改變x不會改變arr的元素
for(auto &x : arr) x是將arr元素的地址拿出來，改變x會改變arr的元素

2.約數個數

求餘數個數——百度百科

【acwing 870. 約數個數】

給定 nn 個正整數 aiai，請你輸出這些數的乘積的約數個數，答案對 10^9+7 取模。

輸入格式

第一行包含整數 nn。

接下來 nn 行，每行包含一個整數 aiai。

輸出格式

輸出一個整數，表示所給正整數的乘積的約數個數，答案需對 109+7109+7 取模。

數據範圍

1≤n≤1001≤n≤100,
1≤ai≤2×1091≤ai≤2×109

輸入樣例：
3
2
6
8
輸出樣例：
12

分別對每一個ai分解質因數後，不斷統計指數個數，不必將ai都相乘得結果後再分解質因數（數據可能過大溢出！）

【代碼實現】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, int>primes;//存儲所有的質因數和它的指數
    
    while (n -- )
    {
        int x;
        cin >> x;
        
        //分解質因數
        for(int i = 2; i <= x / i; i ++)
        {
            if(x % i == 0)
            {
                while(x % i == 0)
                {
                    x /= i;
                    primes[i] ++;
                }
            }
        }
        if(x > 1) primes[x] ++;
    }
    
     //以上過程完成primes就存了所有質因數的指數
    
    LL res = 1;
    for(auto prime : primes) res = res * (prime.second + 1) % mod; 
    // 註：不能寫成 res*= ... 這樣就先取模再乘了（運算符優先級）
    // 每次將乘積結果取模再進行下一次乘：可以保證中間結果不會溢出
    
    cout << res;
    
    
    return 0;
}

3.約數之和

求約數之和——百度百科

【acwing 871 約數之和】

給定 nn 個正整數 aiai，請你輸出這些數的乘積的約數之和，答案對 10^9+7 取模。

輸入格式

第一行包含整數 nn。

接下來 nn 行，每行包含一個整數 aiai。

輸出格式

輸出一個整數，表示所給正整數的乘積的約數之和，答案需對 109+7109+7 取模。

數據範圍

1≤n≤1001≤n≤100,
1≤ai≤2×1091≤ai≤2×109

輸入樣例：
3
2
6
8
輸出樣例：
252

【代碼實現】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, int>primes;//存儲所有的質因數和它的指數
    
    while (n -- )
    {
        int x;
        cin >> x;
        
        //分解質因數
        for(int i = 2; i <= x / i; i ++)
        {
            if(x % i == 0)
            {
                while(x % i == 0)
                {
                    x /= i;
                    primes[i] ++;
                }
            }
        }
        if(x > 1) primes[x] ++;
    }
    
    LL res = 1;
    for(auto prime : primes)
    {
        int p = prime.first, a = prime.second;
        LL t = 1;
        while(a --) t = (p * t + 1) % mod; //求出 p0一直加到p的k的次方的和 （結果可能很大先求模）
        res = res * t % mod; 
    }

    
    cout << res;
    return 0;
}

約數個數與約數之和公式總結

如果 N = p1^c1 * p2^c2 * ... *pk^ck
約數個數： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
約數之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

4.最大公約數（歐幾里得算法）

歐幾里得算法也叫輾轉相除法！

核心原理：

當b不為0時：

（a,b） = (b, a % b)

當b為0時：

（a,b）= a

【代碼實現】

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

三、總結

學習內容源自：
百度百科
acwing算法基礎課

註：如果文章有任何錯誤或不足，請各位大佬盡情指出，評論留言留下您寶貴的建議！如果這篇文章對你有些許幫助，希望可愛親切的您點個贊推薦一手，非常感謝啦

Tags: 數學知識

數論——質數與約數

一、質數

1.質數的判斷

（1）質數的判斷——枚舉法

（2）質數的判斷——試除法

2.分解質因數

（1）分解質因數——短除法

（2）分解質因數——試除法

3.篩質數

1.樸素篩法

2.埃氏篩法

3.線性（歐拉）篩法

對比

二、約數

1.試除法求約數

2.約數個數

3.約數之和

約數個數與約數之和公式總結

4.最大公約數（歐幾里得算法）

三、總結

VirMach 便宜 VPS

QNews

數論——質數與約數

一、質數

1.質數的判斷

（1）質數的判斷——枚舉法

（2）質數的判斷——試除法

2.分解質因數

（1）分解質因數——短除法

（2）分解質因數——試除法

3.篩質數

1.樸素篩法

2.埃氏篩法

3.線性（歐拉）篩法

對比

二、約數

1.試除法求約數

2.約數個數

3.約數之和

約數個數與約數之和公式總結

4.最大公約數（歐幾里得算法）

三、總結

分享此文：

Related Posts

HTML表單

利用圖像二維熵實現視頻信號丟失檢測（Signal Loss Detection）

Intel 12代酷睿i3、賽揚雙雙破5.3GHz！大神感慨N年未見

微信「救命短訊」將正式啟用！

VirMach 便宜 VPS

QNews

熱門文章

熱門搜尋