当前位置:   article > 正文

数学知识---数论(质数和约数)_质数与约数的关系

质数与约数的关系

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 ( n l o g n ) O( nlogn) 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 ( n l o g l o g n ) O(nloglogn) 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 x x 只会被其最小质因子筛掉一次

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

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

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

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

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

筛去 a × i = x a×i=x a×i=x, a ≤ i a≤i ai, a a a x x x的最小质因子得到的合数 x x x

例:
在这里插入图片描述
注意: 3 × 4 3×4 3×4 并未在 i = 4 i=4 i=4时被筛掉, 因为其会在 i = 6 i=6 i=6时以 “最小质因子左乘的方式” 被 2 × 6 2×6 2×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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/609380
推荐阅读
相关标签
  

闽ICP备14008679号