質(zhì)數(shù)

質(zhì)數(shù)：在大于1的整數(shù)中，如果只包含1和本身這倆個約束，就被叫質(zhì)數(shù)或素數(shù)。

質(zhì)數(shù)判定試除法

質(zhì)數(shù)的判定——試除法：如果d能整除n，則n/d再除n，結(jié)果是一個整數(shù)。 d≤n/d。

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;
}

分解質(zhì)因數(shù)試除法

質(zhì)因數(shù)：一個正整數(shù)的倆個因數(shù)都是質(zhì)數(shù)

分解質(zhì)因數(shù)——試除法：

從小到大枚舉所有的質(zhì)因數(shù)，這里我們要的是質(zhì)因子，即因子是質(zhì)數(shù)。

當枚舉到i時，不包含任何2到i-1中的質(zhì)因子

如果n% i==0，則說明n中不包含任何2到i-1之間的質(zhì)因子，i當中也不包含任何2到i-1中的質(zhì)因子

，因此i一定是一個質(zhì)數(shù)。

即只要滿足if(n%i==0)說明i一定是質(zhì)數(shù)。n中最多只包含一個大于sqrt（n）的質(zhì)因子（假設(shè)n中有倆個大于sqrt（n）的質(zhì)因子，倆倆乘一塊之后肯定大于n），因此枚舉的時候可以先把小于根號n的枚舉出來，如果最后剩余的數(shù)大于1，則說明這個數(shù)時大于根號n的質(zhì)因子

void Prime(int n)//求質(zhì)因數(shù)
{
    int count = 0;
    for (int i = 2; i <= n/i; ++i)
    {
        count = 0;
        if (n % i == 0)// i是質(zhì)數(shù)
            while (n % i == 0)
            {
                n = n / i;//n變成另一個因數(shù)，如n原來是6，i是3，n此刻變?yōu)?
                count++;//如果要把一個數(shù)表示成指數(shù)和底數(shù)的形式，如8=2^3，count就是指數(shù),i就是底數(shù)
                
            }
        printf("%d %d\n", i, count);
    }
    if (n > 1) printf("%d 1\n", n);//大于根號n的質(zhì)數(shù)
}

int main()
{
    while (1)
    {
        int n;
        scanf("%d", &n);
        Prime(n);

    }
    return 0;
}

篩質(zhì)數(shù)

把一個數(shù)組里面，所有數(shù)的倍數(shù)刪掉。

如這里第一個數(shù)是2，先把2的所有倍數(shù)刪掉，接著刪除3的所有倍數(shù)，刪4的所有倍數(shù)……

如果某個數(shù)沒有被篩過的話，說明它是一個質(zhì)數(shù)、

上面算法較為麻煩，我們可這樣做，以11為例，我們不需要把2-10的所有數(shù)都進行判斷，我們把2-10中的質(zhì)數(shù)找出來，看11是不是這些質(zhì)數(shù)的倍數(shù)，如果不是則說明11是質(zhì)數(shù)，反之不是質(zhì)數(shù)。即：篩的時候把質(zhì)數(shù)的所有倍數(shù)篩出來即可。

方法一 埃氏篩法

時間復(fù)雜度 O(nloglogn)

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, cnt;
int prime[N];//用來存儲質(zhì)數(shù)
bool st[N];//st代表是否被刪除，true代表被刪除,false代表未刪除
void primes()
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])prime[cnt++] = i;//如果當前數(shù)沒有被篩出去，說明是質(zhì)數(shù)
        for (int j = i + i; j <= n; j += i)//把每個數(shù)的倍數(shù)刪掉
        {
            st[j] = true;
        }
    }
}
int main()
{
    cin>>n;
    primes();
    cout<<cnt<<endl;
    return 0;
}

方法二 線性篩法

合數(shù)：合數(shù)是指在大于1的整數(shù)中除了能被1和本身整除外，還能被其他數(shù)（0除外）整除的數(shù)

這里爭取用合數(shù)的某個質(zhì)因子把每個合數(shù)篩掉，線性篩法要優(yōu)于第一種篩法。

using namespace std;
const int N = 1000010;
int n, cnt;
int prime[N];//用來存儲質(zhì)數(shù)
bool st[N];//st代表是否被刪除，true代表被刪除,false代表未刪除
void primes()
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])prime[cnt++] = i;//如果當前數(shù)沒有被篩出去，說明是質(zhì)數(shù)
        for (int j = 0; prime[j] <= n / i; j++)//從小到大枚舉所有的質(zhì)數(shù),當質(zhì)數(shù)大于某個數(shù)的平方根時，跳出循環(huán)
        {
            st[prime[j] * i] = true;//把primes[j]*i篩掉
            if (i % prime[j] == 0) break;
        }
    }
}
int main()
{
    cin >> n;
    primes();
    cout << cnt << endl;
    return 0;
}

線性篩法核心：n只會被它的最小質(zhì)因子篩掉。

原理：j時從小到大在枚舉所有的質(zhì)數(shù)。下面圖中的pj代表prime[j]

試除法求約數(shù)

如果d是n的約數(shù)，則n/d也一定能整除n，即我們枚舉約數(shù)時，枚舉到d≤n/d即d≤根號n

#include<vector>
vector<int> get_divisors(int n)
{
    vector<int> res;
    for(int i=1;i<=n;++i)
        if (n % i == 0)
        {
            res.push_back(i);//如果i是約數(shù)，就把i放入到數(shù)組中
            if (i != n / i) res.push_back(n/i); //當i不等于n/i時，再把n/i放進來，有可能n是i的平方,如果倆個約數(shù)一樣，數(shù)組里面放的約數(shù)可能會重復(fù)
             //所以這里要判斷一下

        }
    sort(res.begin(), res.end());
    return res;
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);
        for (auto x : res)
            cout << x << " ";
        cout << endl;
    }

    return 0;
}

約數(shù)個數(shù)和約數(shù)之和

約數(shù)個數(shù)：如果一個正整數(shù)N分解完質(zhì)因數(shù)后可這樣表示

則它的約數(shù)個數(shù)可表示為

1~n中1是所有數(shù)的約數(shù)，2是所有以2為倍數(shù)的約數(shù)……，因此1-n當中總共約數(shù)的個數(shù)和1-n當中

總共倍數(shù)的個數(shù)是相同的， 因此我們可以通過統(tǒng)計1-n當中有多少倍數(shù)，進而統(tǒng)計出約數(shù)。

int范圍內(nèi)約數(shù)個數(shù)最多的大概是1500個。

約數(shù)之和：可這樣表示

解題思路：把a1-an分解成這種形式，之后所有指數(shù)+1再相乘

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

const int mod = 1e9 + 7;
int n;
int main()
{
   
    cin >> n;
    unordered_map<int, int> primes;//存儲所有的底數(shù)和指數(shù)
    while (n--)
    {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; ++i)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;//質(zhì)因數(shù)指數(shù)+1
            }
        }
        if (x > 1) primes[x]++;//如果x>1說明x是一個比較大的質(zhì)因數(shù)
    }
    LL res = 1;
    for (auto prime : primes)
    res = res * (prime.second + 1) % mod;
    cout << res << endl;
    return 0;
 }

求約數(shù)和

先求出p的0次方一直加到p的a次方，用這個公式t會由t變?yōu)閜的1次方，一直乘下去會變?yōu)閠的a次方

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

const int mod = 1e9 + 7;
int n;
int main()
{
   
    cin >> n;
    unordered_map<int, int> primes;//存儲所有的底數(shù)和指數(shù)
    while (n--)
    {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; ++i)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;//質(zhì)因數(shù)指數(shù)+1
            }
        }
        if (x > 1) primes[x]++;//如果x>1說明x是一個比較大的質(zhì)因數(shù)
    }
    LL res = 1;
    for (auto prime : primes)
    {
        int p = prime.first, a = prime.second;//p表示底數(shù)，a表示指數(shù)
        LL t = 1;
        //求p的0次方加和一直到p的a次方
        while (a--)
        {
            t = (t * p + 1) % mod;
         
        }
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
 }

最大公約數(shù)（歐幾里得算法）

輾轉(zhuǎn)相除法：一個數(shù)能整除a，也能整除b，這個數(shù)就能整除a+b，也能整除ax+by，求a和b的最大公約數(shù)等于求b和a%b的最大公約數(shù)，文章來源地址http://www.zghlxwxcb.cn/news/detail-425955.html

#include<iostream>
using namespace std;
int gcb(int a, int b)
{
    return b ? gcb(b, a % b) : a;//b如果不是0，返回gcb(b, a % b)，反之返回a
}
int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d", gcb(a, b));
    }
    return 0;
}