数学知识---数论（质数和约数）_质数与约数的关系

1.质数

质数是针对所有大于1的自然数定义的，在大于1的整数中，如果只包含1和本身这两个约数，就被定义成为质数，或者叫素数。

1.1质数的判定—试除法

一个数的因数都是成对出现的：例如12的因数有3和4,2和6
所以我们可以只枚举较小的那一个，即根下n，假设较小的为d，较大的为n/d；

#include<iostream>
#include <algorithm>

using namespace std;

bool is_prime(int x)
{
    if (x < 2) return false;
    //只枚举到较小的约数，不推荐用sqrt(n)，比较慢；i * i <= x容易溢出。不推荐
    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;
}

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

1.2分解质因数—试除法

质因数的定义：

首先我们应该了解一下正常的教学做法：

所以我们只需要进行这些步骤的模拟即可，也就是从2开始遍历循环不停的进行除法：
步骤详解
从2开始往后做除法，第一个能被除开的数一定是原数n的一个质数

for(int i=2;i<=n/i;i++)
        if(n%i==0)
1
2

如果这个数是，那么继续对这个数轮番进行除法，且记录指数

int s=0;
while(n%i==0)
{
	 n/=i;
     s++;	//指数
}           
1
2
3
4
5
6

而如果除到最后n>1那么说明最后的这个n也是n的一个质数
为什么可以这样？
因为
n中最多只包含一个大于根号n的质因子

if(n>1)printf("%d %d\n",n,1);
1

代码实现：

1. 若n是合数，那么它的最大的质因子不会超过sqrt(n)。
2. 若n是质数，那么它只有一个质因子，且该质因子就是它本身，且大于sqrt(n)。

#include<bits/stdc++.h>
using namespace std;

void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){       //n不包含任何从2到i-1之间的质因子（已经被除干净了）
                          //(n%i==0)所以i也不包含何从2到i-1之间的质因子，由质数的定义可知，保证了i是质数
            int s=0;
            while(n%i==0) n/=i,s++;  
            cout<<i<<' '<<s<<endl;
        }
    }  
    if(n>1) cout<<n<<' '<<1<<endl;    //最多只有一个大于根下n的质因子（两个相乘就大于n了）
    cout<<endl;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        divide(a);
    }
}

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

1.3筛质数

（1）普氏筛法
思想：
i从2开始遍历到n，将i所有小于n的倍数全部划掉，剩下的便是质数。
特点：
好记
时间复杂度:$O(nlogn)$
代码

void get_primes() 
{
    for (int i = 2; i <= n; i ++ ) 
    {
        if (!st[i]) primes[cnt ++ ] = i;   //如果没被划过，就存入数组中
        for (int j = 0; j <= n; j += i)//不管是合数还是质数，都用来筛掉后面它的倍数
        {
            st[j] = true;                  //将i的倍数划掉
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

（2）埃氏筛法（埃及人发明的筛法）
思想:
其实跟普氏筛法差不多，只是只用质数去筛，因为合数筛掉的数肯定已经被比它小质数筛掉了，不需要再筛，所以只用质数筛即可。
特点：
思考简单
时间复杂度：$O(nloglogn)$
代码

void get_primes() 
{
    for (int i = 2; i <= n; i ++ ) 
    {
        if (!st[i]) 
        {
            primes[cnt ++ ] = i;
            for (int j = i; j <= n; j += i)
             {    // 放到了里面（唯一区别）
                st[j] = true;//可以用质数就把所有的合数都筛掉；
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

(3) 线氏筛法
核心思想: 合数$x$ 只会被其最小质因子筛掉一次

为方便表述, 定义一个只有本文使用的术语:

“最小质因子左乘的方式” 表: 若 $a\times b=x$, 则$a$ 表示 $x$ 的最小质因子

算法过程
算法的主要逻辑是一个 for i = 2 to n 循环

循环的每一轮会做这样一个事情:

筛去以 “最小质因子左乘 $i$的方式” 得到的合数 $x$, 即:

筛去 $a\times i=x$,$a\le i$,$a$为$x$的最小质因子得到的合数 $x$

例:

注意: $3\times 4$ 并未在 $i=4$时被筛掉, 因为其会在 $i=6$时以 “最小质因子左乘的方式” 被 $2\times 6$ 筛掉

代码

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;   // 循环到 i 时, 算法暗含 1 ~ i-1 的所有合数都被筛掉, 只剩素数
        for(int j = 0; primes[j] <= n / i; j++) // 算法不会闲的没事干筛去 primes[j] * i > n 的数
        {
            st[primes[j] * i] = true;   // 筛掉以最小质因子左乘 i 的方式得到的合数
            if(i % primes[j] == 0) break;   
            // 出现 i 是 primes[j] 的倍数情况时, 
            // primes[j] 后一个质数左乘 i 就不是 "最小质因子左乘的方式" 了, 
            // 如 i = 4, primes[j] = 2, primes[j] 后一个质数是 3, 
            // 3 * 4 显然不是 "最小质因子左乘的方式", 而应该是 2 * 6
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.约数

2.1试除法求约数

代码：

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

using namespace std;

int n;

void get_divisors(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) {  // 避免 i==n/i, 重复放入 （n是完全平方数
                res.push_back(n / i);
            }
        }
    }

    sort(res.begin(), res.end());
    for (auto item : res) {
        cout << item << " ";
    }
    puts("");
}

int main()
{
    cin >> n;
    while (n--) {
        int x;
        cin >> 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
34
35
36
37
38
39
40
41

2.2约数个数

基于算数基本定理

#include<iostream>
#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++)
        {
            while(x % i == 0)
            {
                x /= i;
                primes[i]++;//指数累加
            }
        }
        if(x > 1)   primes[x] ++;
    }
    
    LL res = 1;
    for(auto prime : primes)    res = res * (prime.second + 1) % mod;

    cout<<res<<endl;
    
    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

2.3约数之和

while (b -- ) t = (t * a + 1) % mod;
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;
}


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
47
48

2.4最大公约数—欧几里得算法（辗转相除法）

解法一：直接用辗转相除法求解

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
//选其一即可
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

/*int gcd(int x,int y){
    if(x % y == 0)return y;
    return gcd(y,x % y);
}*/
int main() {
    cin >> n;
    while(n--){
        cin >> a >> b;
        cout << gcd(a,b) << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法2：使用STL中的__gcd函数
（注意！函数前面有两个下划线哦。即：是“__gcd”而不是“_gcd”）
库函数

#include<algorithm>
1

#include<bits/stdc++.h>//万能头文件
using namespace std;//这句话一定不能忘哦！
int n,a,b;
int main() {
    cin >> n;
    while(n--){
        cin >> a >> b;
        cout << __gcd(a,b) << endl;//调用STL函数
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11