质数和约数算法优化

提示：例题中的注释是精华

1 质数

质数：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数或素数

1.1 质数的判定——试除法

时间复杂度：$\sqrt{n}$

如果d能整除n的话，那么$n/d$也能整除n
在枚举的时候只枚举d<=$n/d$的数 $d<=\sqrt{n}$ 即可

1.1.1 模板

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;
}
1
2
3
4
5
6
7
8

1.1.2 例题

AcWing 866. 试除法判定质数

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

using namespace std;
int n;

void isprime (int x)
{
    if(x < 2) {
        puts("No");
        return;
    }
    for (int i = 2; i <= x / i; i ++)
    {
        if(x % i == 0)
        {
            puts("No");
            return;
        }
    }
    puts("Yes");
}


int main ()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int x;
        scanf("%d", &x);
        isprime(x);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

1.2 分解质因数——试除法

非质数都可以分解成若干质数相乘的形式，而将其分解就是分解质因数
性质：n当中最多只包含一个大于$\sqrt{n}$的质因子
一个数的除了 1 之外最小的因数一定是质数

1. 质因子: 能整除给定正整数的质数
2. 每个合数都可以写成几个质数相乘的形式 x=p1p2…*pn
3. 质因子如重复可以用指数表示
4. 质数:只有一个质因子的正整数,质数>=2
5. 1没有质因子
6. 质数=素数,因数=约数

1.2.1 模板

时间复杂度最坏O($\sqrt{n}$)，最好是$logn$

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)// 每次从低位的质数相除，这样稍高位的合数就没了因子了，所以满足条件的一定是质数
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;// 将最小的质数除掉，剩下的数的求新的最小因数
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;//说明剩余的x是一个质数在根号n内没有因子了
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

1.2.2 例题

AcWing 867. 分解质因数

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

using namespace std;

int n;

void divide (int x)
{
    for (int i = 2; i <= x / i; i ++)// 优化循环次数，最后x单独判断
    {
        if (x % i == 0)// 因为是从小到大遍历所以，x的最小因数一定是质数,所以i一定是质数
        {
            int s = 0;// 这里s要定义到if内因为是每一个质数的指数
            while(x % i == 0) x /= i, s ++;// 把i这个因子除干净，后这样新的数的最小因子就又是比上个i大的新的质数
            printf("%d %d\n", i, s);
        }
    }
    if (x > 1) printf("%d %d\n", x, 1);// 最后x是质数的话根号n内他就没有因子了，就要将它输出
    cout << endl;
}

int main ()
{
    cin >> n;

    while (n -- )
    {
        int x;
        scanf("%d", &x);

        divide(x);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

1.2 筛质数

一个数p如果不是1~p - 1的倍数就说明它是一个质数
质数定理：1~n中有$\frac{n}{\ln n}$个质数

埃氏筛法：是将一个数的倍数筛掉
线性筛法: n只会被它的最小质因子筛掉

1.2.1 内容

• 从小到大枚举所有的质数
• 每次将当前的质数和i的乘积筛掉
• 当（i % primes[j] == 0）break;//此时primes[j] 一定是最小质因子

1.2.2 最简单的做法

i从2开始枚举将i的倍数标记成合数

时间复杂度是O(n$\log n$)

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_prime(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[j] = true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2.3 埃氏筛法

埃氏筛法是将上面的方法进行优化，这标记质数的倍数，但是存在重复标记的问题

时间复杂度:实际是O(nlogn logn),近似O(n）

// 朴素筛分求素数
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.2.4 线性筛法

线性筛法是将每个和数用它的最小质因子筛掉，且只用最小值因子筛掉，保证只筛一次，所以是线性的

时间复杂度：O(n)

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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 ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.2.4.1 例题

AcWing 868. 筛质数

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

using namespace std;

const int N = 1e6 + 10;

int primes[N], cnt;// 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 ++)// 从小到大枚举已经添加的质数
        {
            st[primes[j] * i] = true;//当不满足i % primes[j] 是说明primes[j] 不是i的最小质因子，那么primes[j] 就是primes[j] * i 的最小质因子
            if (i % primes[j] == 0) break;// 当i % primes[j] == 0时说明primes[j] 是i的最小质因子此时还满足 primes[j] 是 primes[j] * i 的最小质因子        }

            // 当是当进行下一次循环时，primes[j + 1] * i 因为i中有最小因子primes[j] 所以primes[j + 1] * i 就只能被primes[j] 筛掉，否则就重复筛了
        }
    }
}

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

    get_primes(n);
    printf("%d", cnt);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2 约数

又称一个数的因数

2.1 试除法求约数

2.1.1 set容器的基本概念

• 所有元素都会在插入set容器时自动排序
• set/multiset属于关联式容器，底层是二叉树
• set容器不允许存在重复元素
• multiset允许存在重复元素

2.1.2 模板

时间复杂度：

void get_divisors(int x)
{
    set<int> s;
    for (int i = 1; i <= x / i; i ++)
    {
        if (x % i == 0) s.insert(i), s.insert(x / i);
    }
    for (auto item : s)
        printf("%d ", item);
    puts("");
    
}
1
2
3
4
5
6
7
8
9
10
11
12

2.1.3 例题

AcWing 869. 试除法求约数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

void get_divisors(int x)
{
    set<int> s;
    for (int i = 1; i <= x / i; i ++)
    {
        if (x % i == 0) s.insert(i), s.insert(x / i);// x能被i整除i是其中一个因数，那么另一个因数是x / i
    }
    for (auto item : s)// set容器会自动排序
        printf("%d ", item);
    puts("");

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

    for (int i = 0; i < n; i ++)
    {
        int x;
        scanf("%d", &x);

        get_divisors(x);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

2.2 约数和定理和约数个数定理

bilibili的up讲解

2.2.1 约数个数定理

内容：首先，分解质因数，这样通过利用质因数进行“造”约数就可以得到约数
而每个质因数都可以有0,1……n 这n + 1个取法
因此约数的个数就是将
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1)

2.2.2 例题

AcWing 870. 约数个数

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

using namespace std;

typedef long long LL;

const int N = MOD = 1e9 + 7;
unordered_map<int, int> primes;


void divide(int x)
{
    for (int i = 2; i <= x / i; i ++)
    {
        while(x % i == 0) x /= i, primes[i] ++;// 不需要按顺序输出就不用按分解质因数那样用k记录
    }
    if (x > 1) primes[x] ++;
}

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

    while (n --)
    {
        int x;
        scanf("%d", &x);

        divide(x);
    }

    LL res = 1;
    for (auto prime : primes)
        res = res * (prime.second + 1) % MOD; // 不能写成res *= 因为这样会先取模，而这样写就是后取模

    printf("%d", res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2.2.3 约数和定理

通过“造”的方法，每个质因子与另外的一些质因子进行组合可以得到相应的组合：
(p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)
在计算每一个pn时使用了秦九韶算法

简单来说就是将一个多项式层层剥离，最后剥成一个ax + b的形式而其中a是最前面一个次方的系数，b是后面一个次方的系数，计算的结果就可以作为下一个多项式的系数

2.2.4 例题

AcWing 871. 约数之和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;

const int N = 2e9, MOD = 1e9 + 7;
int n;

unordered_map<int, int> primes;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++)
    {
        while (x % i == 0) x /= i, primes[i] ++;
    }
    if (x > 1) primes[x] ++;
}

int main()
{
    cin >> n;

    int sum = 0;
    for (int i = 0; i < n; i ++)
    {
        int x;
        scanf("%d", &x);
        divide(x);
    }

    LL res = 1;
    for (auto prime : primes)// 从这里处理用上了秦九韶算法，其余与求约数个数相同
    {
        int x = prime.first, k = prime.second;
        LL temp = 1;
        for (int i = 0; i < k; i ++)
            temp = (temp * x + 1) % MOD; // 当i = 0时一开始的系数是1，后面加1是因为后面的系数都是1，最后的系数也是1
        res = res * temp % MOD;
    }
    printf("%d", res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

2.3 最大公因数

欧几里得算法
其中最关键的是（A, B） = (B, R) ->A和B的最大公因数和B和R的最大公因数相等，递推到最后可以发现余数为零时的R就是A, B的最大公因数

2.3.1 欧几里得算法（辗转相除法）

2.3.1.1 模板

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;//在最后一轮递归的过程中 a % b == 0 就说明余数为零， 返回的a是上一轮的b就是上面提到的R
}
1
2
3
4

2.3.1.2 例题

AcWing.872. 最大公约数

#include <iostream>
#include <cstring>
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3 参考文献

数学知识（一）
约数和定理和约数个数定理
秦九韶算法
欧几里得算法