一、质数

【相关概念】

因数:一整数被另一整数整除,后者即是前者的因数,如1,2,4都为8的因数
倍数:一个数能够被另一数整除,这个数就是另一数的倍数。如15能够被3或5整除,因此15是3的倍数,也是5的倍数。
质数:一个数除了1和它本身没有其他的因数,就叫质数。如2,3,5,7,
和数:一个数除了1和它本身还有其他的因数,(至少有3个因数)就叫合数。如4,6,8,9

1.质数的判断

(1)质数的判断——枚举法

//根据质数定义判断 一个数是否为质数 O(n)
bool is_prime(int n)  // 判定质数
{
    if(n < 2) return false;
    for (int i = 2; i < n; i ++ )
    {
        if(n % i == 0)
            return false;
    }

    return true;        
}

(2)质数的判断——试除法

上述短除法是从头到尾枚举判断,时间复杂度相对很高,其实没有必要枚举1~n所有的数然后判断!

思路:

1~根号n之间的数都找一遍,看看有没有一个数是n的因子,之所以找到根号n,是因为因子都是成对出现的,假设in的因子,那么在根号n后面必定有一个数n/in的因子。(只枚举每一对因子中较小的数)。

i | n 那么 n/i | n ,即枚举i的范围从2~n/i即可(只枚举每一对因子中较小的数)

​ i*i <= n 所以 i <= sqrt(n),即时间复杂度O(sqrt(n))

//试除法 判断一个数是否为质数 O(sqrt(n))
bool is_prime(int n)  
{
    if(n < 2) return false;
    for (int i = 2; i <= n / i; i ++ )
    {
        if(n % i == 0)
            return false;
    }

    return true;        
}

2.分解质因数

【相关概念】

什么是质因数?

​ 如果一个数的因数是质数,那么这因数就是质因数!

什么是分解质因数?

​ 把一个合数分解成若干个质因数的乘积的形式,即求质因数的过程叫做分解质因数。

(1)分解质因数——短除法

小学时分解质因数的方法——短除法

分解质因数只针对合数(质数就只有本身和1两个因数,不能分解)。一个数分解质因数,要从最小的质数除起(依次除于质数2 3 5....),一直除到结果为质数为止。分解质因数的算式叫短除法.

image

【参考代码】

短除法分解质因数——O(n)

void divide(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(n % i == 0)//i一定是质数
        {
            int s = 0;
            while(n % i == 0)//短除法分解质因数
            {
                n /= i;
                s ++;//统计i出现的次数
            }
            printf("%d %dn", i, s);
        }
    }
}

(2)分解质因数——试除法

上述短除法分解质因数,要从最小的质数除起(依次除于质数2 3 5....)一直到n,时间复杂度为O(n),其实也没必要枚举1~n所有质数然后进行判断!

这里有一个重要的性质

n中最多只含有一个大于sqrt(n)的质因子

​ 证明:通过反证法:如果有两个大于sqrt(n)的因子,那么相乘会大于n,矛盾。证毕

于是我们发现最多只有一个大于sqrt(n)的因子,对其进行优化。先考虑比sqrt(n)小的,代码和质数的判定类似

最后如果n还是>1,说明此时的n就是大于sqrt(n)的唯一质因子,输出即可。(特判)

【参考代码】

试除法分解质因数——O(sqrt(n))

void divide(int n)
{
    for(int i = 2; i <= n / i; i ++)
    {
        if(n % i == 0)//i一定是质数
        {
            int s = 0;
            while(n % i == 0)//短除法分解质因数
            {
                n /= i;
                s ++;//统计i出现的次数(指数)
            }
            printf("%d %dn", i, s);
        }
    }
    
    if(n > 1) printf("%d %dn", n, 1);//当n没有变化的时候,输出本身和1
}

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

3.筛质数

求某个数n有多少个质数?

1.朴素筛法

枚举i:2~n从前往后把每个数对应的倍数都删除掉,这样筛过之后,所有剩下的数都是质数。(每个数i不存在该数的约数)

时间复杂度:O(nlogn)

int prime[N], cnt;//prime数组存储质数,cnt统计个数
bool st[N];//标记是否被筛过

//朴素筛法-O(nlogn)
void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])//如果没被筛过
        {
            prime[cnt ++] = i;
        }
        //把i的每一个倍数结果删掉
        for(int j = i + i; j <= n; j += i) st[j] = true;
    }
}

2.埃氏筛法

埃氏筛法是对朴素筛法的一种优化方式,我们并不需要把2~n的每一个数的倍数都删掉,可以只把所有质数的倍数删掉

埃氏筛法:我们会发现4的倍数也是2的倍数,所有我们只需要把所有质数的倍数删除就好。
时间复杂度:O(n * loglogn),近似O(n)

//朴素筛法-O(n * loglogn)
void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])//如果没被筛过
        {
            prime[cnt ++] = i;
            //把质数i的每一个倍数结果删掉
        	for(int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}

3.线性(欧拉)筛法

埃氏筛法的缺陷 :对于一个合数,有可能被筛多次。例如 30 = 2 * 15 = 3 * 10 = 5*6……那么如何确保每个合数只被筛选一次呢?我们只要用它的最小质因子来筛选即可,这便是欧拉筛法。

欧拉筛法的基本思想 :在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。

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

// 合数 = 质数(最小) x 因数
//线性筛法-O(n)
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        // 如果没被筛过 将素数记下来
        if(!st[i]) prime[cnt ++] = i;
        // 从小到大枚举所有质数
        for(int j = 0; i * prime[j] <= n; j ++)//primes[j]*i<=n,把大于n的合数都筛了就没啥意义了
        {
            // 每个合数只被它的最小质因子筛掉
            st[i * prime[j]] = true;
            
            if(i % prime[j] == 0) break;// prime[j]一定是(合数)i的最小质因子(从小到大枚举质数嘛) 
        }
    }
}
  1. i % prime[j] == 0

​ prime[j]一定是(合数)i的最小质因子,prime[j]也一定是prime[j] * i的最小质因子

  1. i % prime[j] != 0

    没有找到i的任何一个质因子,说明当前prime[j]一定小于i的所有质因子(质数是从小到大枚举的),prime[j]也一定是prime[j] * i的最小质因子

任何一个合数一定会被筛掉:

​ 对于任何一个合数,它都会有且只有一个最小的质因子!因此只会被筛一次!

对比

image

二、约数

约束定义:

​ 约数又称因数,整数A除以整数B(B≠0) 除得的商正好是整数而没有余数,我们就说A能被B整除,或B能整除A。A称为B的倍数,B称为A的约数。

质数只有两个约数:1和它本身。

合数至少有3个约数。

1.试除法求约数

思路:

O(sqrt(n))的做法,枚举一个较小的因子,另一个直接用原数去除。

注 意 完 全 平 方 数 只 要 加 入 一 个 因 子 。

一个数d要是能被n整除,那么n/d也能被n整除,即约数也是成对存在的,我们只需枚举较小的约数即可,另一个通过 n / d求出!从1枚举到sqrt(n)即可,即i <= n /i

注:

​ 当n为完全平方数时,约数只存储一次,不能够重复存储!因此要注意特判!

【代码实现】

vector<int> get_divisor(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) res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

【acwing 869 试除法求约数】

给定 nn 个正整数 aiai,对于每个整数 aiai,请你按照从小到大的顺序输出它的所有约数。

输入格式

第一行包含整数 nn。

接下来 nn 行,每行包含一个整数 aiai。

输出格式

输出共 nn 行,其中第 ii 行输出第 ii 个整数 aiai 的所有约数。

数据范围

1≤n≤1001≤n≤100,
2≤ai≤2×1092≤ai≤2×109

输入样例:

2
6
8

输出样例:

1 2 3 6 
1 2 4 8 

【代码实现】

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

using namespace std;

vector<int> get_divisor(int n)
{
    vector<int> res;
    
    //将成对的约数存下来,平方数只存一次
    for(int i = 1; i <= n / i; i ++)
    {
        if(n % i == 0)
        {
            res.push_back(i);//较小的约数
            //特判 防止重复存储n为平方数的情况 
            if(i != n / i) res.push_back(n / i);//存另一个约数 较大的约数
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
        int a;
        scanf("%d", &a);
        
        auto res = get_divisor(a);
        for(auto c : res) cout << c << " ";
        puts("");
    }
    
    return 0;
}

for(auto x : arr) 遍历方式, x只是将arr里的元素复制下来,改变x不会改变arr的元素
for(auto &x : arr) x是将arr元素的地址拿出来,改变x会改变arr的元素

2.约数个数

求余数个数——百度百科

image

【acwing 870. 约数个数】

给定 nn 个正整数 aiai,请你输出这些数的乘积的约数个数,答案对 10^9+7 取模。

输入格式

第一行包含整数 nn。

接下来 nn 行,每行包含一个整数 aiai。

输出格式

输出一个整数,表示所给正整数的乘积的约数个数,答案需对 109+7109+7 取模。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2×1091≤ai≤2×109

输入样例:

3
2
6
8

输出样例:

12

分别对每一个ai分解质因数后,不断统计指数个数,不必将ai都相乘得结果后再分解质因数(数据可能过大溢出!)

【代码实现】

#include <iostream>
#include <cstring>
#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 ++)
        {
            if(x % i == 0)
            {
                while(x % i == 0)
                {
                    x /= i;
                    primes[i] ++;
                }
            }
        }
        if(x > 1) primes[x] ++;
    }
    
     //以上过程完成primes就存了所有质因数的指数
    
    LL res = 1;
    for(auto prime : primes) res = res * (prime.second + 1) % mod; 
    // 注:不能写成 res*= ... 这样就先取模再乘了(运算符优先级)
    // 每次将乘积结果取模再进行下一次乘:可以保证中间结果不会溢出
    
    cout << res;
    
    
    return 0;
}

3.约数之和

求约数之和——百度百科

image

image

【acwing 871 约数之和】

给定 nn 个正整数 aiai,请你输出这些数的乘积的约数之和,答案对 10^9+7 取模。

输入格式

第一行包含整数 nn。

接下来 nn 行,每行包含一个整数 aiai。

输出格式

输出一个整数,表示所给正整数的乘积的约数之和,答案需对 109+7109+7 取模。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2×1091≤ai≤2×109

输入样例:

3
2
6
8

输出样例:

252

【代码实现】

#include <iostream>
#include <cstring>
#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 ++)
        {
            if(x % i == 0)
            {
                while(x % i == 0)
                {
                    x /= i;
                    primes[i] ++;
                }
            }
        }
        if(x > 1) primes[x] ++;
    }
    
    LL res = 1;
    for(auto prime : primes)
    {
        int p = prime.first, a = prime.second;
        LL t = 1;
        while(a --) t = (p * t + 1) % mod; //求出 p0一直加到p的k的次方的和 (结果可能很大先求模)
        res = res * t % mod; 
    }

    
    cout << res;
    return 0;
}

约数个数与约数之和公式总结

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数: (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和: (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

4.最大公约数(欧几里得算法)

欧几里得算法也叫辗转相除法!

核心原理:

image

当b不为0时:

(a,b) = (b, a % b)

当b为0时:

(a,b)= a

【代码实现】

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

三、总结

学习内容源自:
百度百科
acwing算法基础课

注:如果文章有任何错误或不足,请各位大佬尽情指出,评论留言留下您宝贵的建议!如果这篇文章对你有些许帮助,希望可爱亲切的您点个赞推荐一手,非常感谢啦

内容来源于网络如有侵权请私信删除