目录

质数

试除法判定质数 

分解质因数

筛质数

约数

试除法求约数

约数个数

约数之和

最大公约数

---

质数

试除法判定质数 

这个算法广为人知，这里就不证明了，解释一下 i<=√n 的写法

1、不推荐写成i<=sqrt(n)

首先需要引入头文件#include<cmath>麻烦，其次每次循环都要调用sqrt()函数，速度变慢了；

2、强烈不推荐写成 i*i<=n

如果 i 的值比较大， i*i 极有可能有爆int的风险，影响质数判断且很难debug；

3、强烈推荐用 i<=x / i 写法

不需要调用函数且绝对不会有数值过大的风险

#include <iostream>
#include <algorithm>

using namespace std;

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

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }

    return 0;
}

分解质因数

本词条由“科普中国”科学百科词条编写与应用工作项目 审核 。 

质因子（或质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。 

即：n=p1^a1 * p2^a2 *p3^a3.....pn^an（p为质数，a为幂）

证明1：

循环里面的 i 一定是一个质数：假如 i 是一个合数，那么它一定可以分解成多个质因子相乘的形式，这多个质因子同时也是 x 的质因子且比 i 要小，而比 i 小的数在之前的循环过程中一定是被条件除完了的，所以 i 不可能是合数，只可能是质数

证明2：

if (x > 1) cout << x << ' ' << 1 << endl;

比sqet(n)大的质因子x最多只有1个，因为如果该质因子x数量大于一个，则x*x>n，是不可能的，所以比sqet(n)大的质因子x最多只有1个

那么我们只需要找小于sqrt（n）的所有质因子，然后如果n的值还大于1，说明仍然存在质因子，又因为大于sqrt（n）的质因子只有一个，所以直接输出该值并标记幂为1

#include <iostream>
#include <algorithm>

using namespace std;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)//见证明1：如果该条件成立，i一定是质数
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;//最多只有一个大于平方根下n的质因子（两个相乘就大于n了）
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

筛质数

 诶氏筛法 O(nloglogn)

 根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。 

反向思考：将2到n中，所有质数的倍数删除，那么剩下的就只有质数

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;//存质数与质数个数
bool st[N];//用于装合数

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])//如果不是合数（是质数）
        {
            primes[cnt ++ ] = i;//存质数
            for (int j = i + i; j <= n; j += i)//将质数的倍数（合数）装入st[]
                st[j] = true;
        }

    }//最后primes[]存2到n所有质数，st[]装所有合数
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

线性筛法 O(n)

if(i%primes[j]==0) break;

分两种情况：

情况1 i%primes[j]!=0

当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]小于 i 的最小质因子,所以primes[j]*i的最小质因子就是primes[j]; 

情况2 i%primes[j]==0

当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
prime[j]，当发现primes[j]是i最小质因子的时候,如果再继续进行的话，我们就把 prime[j+1]*i 这个数筛掉了,虽然这个数也是合数，但是我们筛掉它的时候并不是用它的最小质因数筛掉的，而是利用 prime[j+1] 和 i 把它删掉的，也就是说这个数的最小质因数其实是prime[j],如果我们不在这里退出循环的话，我们会发现有些数是被重复删除了的。 

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

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

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )//primes[j]*i<=n 筛掉小于n的合数
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;//保证线性筛质数
        }
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

约数

试除法求约数

若 i 是N的约数，则 N/i 也是N的约数。换言之，约数总是成对出现的（(除了对于完全平方数，√N会单独出现)。

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

using namespace std;

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);//存储成对出现的约数
            if (i != x / i) res.push_back(x / i);//除了对于完全平方数，√N会单独出现
        }
    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;
}

约数个数

约数个数定理： 

 根据约数个数定理，我们只需要分解质因数，然后直接套公式即可

分解质因数如上质数部分

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;//存储质数p和对应的幂a

    while (n -- )
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )//分解质因数
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;//公式(a1+1)*(a2+1)*....*(ak+1)

    cout << res << endl;

    return 0;
}

约数之和

约数和定理_百度百科 (baidu.com)

例题：正整数360的所有正约数的和是多少？

解：将360分解质因数可得

360=2^3*3^2*5^1

由约数和定理可知，360所有正约数的和为

(2^0+2^1+2^2+2^3)×(3^0+3^1+3^2)×(5^0+5^1)=(1+2+4+8)(1+3+9)(1+5)=15×13×6=1170

可知360的约数有1、2、3、4、5、6、8、9、10、12、15、18、

20、24、30、36、40、45、60、72、90、120、180、360；则它们的和为

1+2+3+4+5+6+8+9+10+12+15+18+20+24+30+36+40+45+60+72+90+120+180+360=1170

总结：

分解质因数后，约数和为

 值得注意的是：

while (b -- ) t = (t * a + 1) % mod;

若b=0，t=1;b=1,t=p+1 以此类推

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, 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 ++ )//分解质因数
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto p : primes)//套公式
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;//求累加
        res = res * t % mod;//求累乘
    }

    cout << res << endl;

    return 0;
}

最大公约数

辗转相除法求最大公约数，一行代码，背就完事了 

#include <iostream>
#include <algorithm>

using namespace std;


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


int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}

值得注意的是，可以调用STL；但是速度比自己手写慢个5倍左右！！

#include<iostream>
#include<algorithm>
using namespace std;！
int n,a,b;
int main() {
    cin >> n;
    while(n--){
        cin >> a >> b;
        cout << __gcd(a,b) << endl;//调用STL函数
    }
    return 0;
}