数据结构与算法学习笔记----质数

数据结构与算法学习笔记----质数

@@ author: 明月清了个风
@@ first publish time: 2024.12.23

ps⭐️质数的判定，分解和筛选，包含了三道题目

什么是质数

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

Acwing 866. 试除法判定质数

[原题链接](866. 试除法判定质数 - AcWing题库)

给定$n$个正整数$a_i$，判定每个数是否是质数。

输入格式

第一行包含整数$n$，

接下来$n$行，每行包含一个正整数$a_i$。

输出格式

共$n$行，其中第$i$行输出第$i$个正整数$a_i$是否为质数，是则输出Yes,否则输出No。

数据范围

$1\le n\le 100$,

$1\le a_i\le 2^{31}-1$

思路

试除法是从定义出发的判断思路，也就是判断有没有除了$1$和这个数本身之外的因数。

有两个注意点：

1. 如果有一个数$d$能被数$n$整除，那么$n/d$也能被$n$整除，因数是成对出现的，因此我们在判断时只需要判断到$\sqrt{n}$即可。
2. 代码中的循环终止条件i <= n / i，而不写成i * i <= n，因为这样存在溢出风险。

因为只要判断到$\sqrt{n}$，所以时间复杂度为$O(\sqrt{n})$。

代码

#include <iostream>
#include <cstring>

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

Acwing 867. 分解质因数

[原题链接](867. 分解质因数 - AcWing题库)

给定$n$个正整数$a_i$，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数$n$，

接下来$n$行，每行包含一个正整数$a_i$。

输出格式

对于每个正整数，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

$1\le n\le 100$,

$2\le a_i\le 2\times 10^9$

思路

同样使用试除法进行分解，对于碰到的每个质因数都将他除干净记录次数，具体的看代码吧

时间复杂度为$O(\sqrt{n})$，但不一定会到这个数，这是最坏的情况。

代码

#include <iostream>
#include <cstring>

using namespace std;

void divide(int x)
{
    for(int i = 2; i <= x / i; i ++)
    {
        if(x % i == 0)   // 如果是一个因数，则记录次数，这里能够保证这个因数是质因数，因为每次碰到了因数都会除干净，并且从2开始就是质因数
        {
            int s = 0;
            while(x % i == 0)
            {
                x /= i;
                s ++;
            }
            cout << i << ' ' << s << endl;
        }
    }
    
    if(x > 1) cout << x << ' ' << 1 << endl;  // 一个数最多有一个大于根号x的质因数，如果有两个乘起来就大于x了，因此最后还要判断一下
    puts("");
}

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

Acwing 868. 筛质数

[原题链接](868. 筛质数 - AcWing题库)

给定一个正整数$n$，请你求出$1\sim n$中质数的个数

输入格式

共一行，包含整数$n$。

输出格式

共一行，包含一个整数，表示$1\sim n$中质数的个数

数据范围

$1\le n\le 10^6$

思路

首先肯定还是从定义出发，只要筛选掉所有的合数剩下的就是质数了，因此可以将从小到大开始，将每个数的倍数就筛掉，代码如下

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)   // 将每个数的x倍都筛掉
            st[j] = true;   // 筛掉的数标记为true
    }
}

这样的筛选时间复杂度为$O(n\ln n)=O(n{\log }_{e}n)\approx O(n\log n)$

这里可以做出一点优化，我们在筛选时可以只用质数去筛选，将第二重循环放在判断里面，这样的话所有的合数都会被一个质数筛掉，根据质数定理：$1\sim n$中有$\frac{n}{\ln n}$个质数，在上面的筛选中时间复杂度为$n(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n})\approx n\ln n$，但是只用质数筛后，我们本来要计算$n$个数，现在只需要计算$\frac{n}{\ln n}$个数，因此时间复杂度变为$\frac{n\ln n}{\ln n}\approx n$，也就是$O(n)$，但是这是一个粗略估计，真实的复杂度为$O(n\log \log 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)   // 将每个数的x倍都筛掉
            	st[j] = true;   // 筛掉的数标记为true
        }
    }
}

对于上述筛法还可以进一步优化，因为在上面的筛选过程中，一个合数可能会被筛选多次，比如对于$6$来说，他会被$2$和$3$分别筛选一次，那么如果省去这样多余的步骤呢，线性筛法完成了这样的优化，**通过优化合数的标记方式，使每个合数都只被筛选一次，从而达到了线性时间复杂度。**下面首先给出线性筛选的代码

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. 如果$i$是质数，那么会被记录在primes[]数组里

2. 如果$i$是合数，他会被其最小质因子标记为合数。

   • 为什么是最小质因子

     因为我们从小达到遍历所有质数primes[]，有两种情况：

     a. 当i % primes[j] == 0时跳出循环，此时primes[j]肯定是i的最小质因子；

     b. 当i % primes[j] != 0时，我们会将primes[j] * i标记为合数，对于primes[j] * i来说，因为i % primes[j] != 0并且primes[j]是从小到大枚举的，因此primes[j]肯定不是i的最小质因子，且小于其最小质因子，但是对于primes[j] * i来说，因为i的最小质因子大于primes[j]，因此primes[j] * i的最小质因子为primes[j]。

     这样就确保了每个合数都只会被其最小质因子筛掉，每个数又只有一个最小质因子，因此整个算法是线性的。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010;

int n;
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 ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    cin >> n;
    
    get_primes(n);
    
    cout << cnt << endl;
    
    return 0;
}