【重拾算法第一天】质数约数欧拉筛 埃氏筛GCD

1.素数

素数（Prime Number）是指大于1的自然数，只有两个正因数：1和它自身。换句话说，素数是不能被其他自然数整除的数。

1.1小素数的判定

判定一个数是否为素数 ，当N ≤  时， 用试除法 ， 当n >  时 ， 用Miller_Rabin算法

根据素数的定义，可以直接得到试除法 ， 用[2,n - 1] 内的所有数着除n，如果不能整除 ， 就是素数，很容易发现 可以把[2 , n - 1] 缩小到 , [2,]

试除法的时间复杂度为O（n），N ≤  时够用 ，  以下为试除法的实现代码：

#define int long long
bool is_prime(int n)
{
    if(n <= 1) return false;
    for(int i = 2;i * i <= n;i ++)
    {
        if(n % i == 0) return false;
    }
    return true;
}
//i * i <= n 也可以写成 i < n / i

1.2大素数的判定

本章介绍大素数的判定的两种方法

如果N 非常大  试除法就不够用了

一般采用Miller_Rabin素行测试算法  ，由于这个算法过于复杂 就不在这里介绍这个算法了

2.分解质因数

什么是质因数？

质因数（Prime Factor）是指一个整数的质数因子。换句话说，质因数是能够整除该整数的质数。每个大于1的自然数都可以被唯一分解为质因数的乘积，这称为质因数分解。

void divide(int x)
{
    for(int i = 2;i <= x / i;i ++)
    {
        if(x % i == 0)  //以x为底数
        {
            int s = 0; //s为指数
            while(x % i == 0) x /= i , s++;
            cout << i << ' ' << s << endl;
        }
    }
    if(x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

3.素数筛

主要用于筛选1 ~ n 中的素数的个数

有两种方法 ：

3.1.埃氏筛发（传统的  时间复杂度O(nlognlongn）)

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int prime[N]; //存储素数  visit[i]为false的项
bool vis[N];  //true表示被筛掉 不是素数
int E_sieve(int n)  //埃氏筛法
{
    int k = 0; //统计个数
    for(int i = 0;i <= n;i ++) vis[i] = false;
    for(int i = 2;i <= n;i ++)
    {
        if(!vis[i])
        {
            prime[k++] = i;
            for(int j = 2 * i;j <= n;j += i)
            // 可以优化成 j = i * i
            {
                vis[j] = true;
            }
        }
    }
    return k;
}
int main()
{
    int n;
    cin >> n;
    cout << E_sieve(n) << endl;
    return 0;
}

3.2.欧拉筛（时间复杂度O（n））

欧拉筛的原理：

欧拉筛是一种线性筛法 ， 能在O（n） 的线性时间求得1~N内所有的素数  欧拉筛是对埃氏筛的一种改进

原理：一个合数肯定有一个最小的质因数；让没个合数只被他的最小质因数筛选一次 ，达到不重复筛的目的；

具体操作：

1：逐一检查2~n的所有数  第一个检查的是 2 ， 他是第一个素数

2：当检查到第i个数时，利用已经求得的素数去筛掉对应的合数x ， 而且是用x的最小质因数去筛

代码实现：

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

const int N = 1e6 + 10;  // 定义常量N为1000010，表示素数的上限
int prime[N];            // 存储素数的数组，visit[i]为false的项
bool vis[N];             // vis[i]表示i是否被筛掉，true表示i不是素数

// 欧拉筛法，返回小于等于n的素数个数
int euler_sieve(int n) {
    int cnt = 0;  // 计数器，用于记录素数的个数
    memset(vis, 0, sizeof(vis));  // 初始化vis数组，所有项设为false
    memset(prime, 0, sizeof(prime)); // 初始化prime数组

    // 从2开始，遍历到n
    for (int i = 2; i <= n; i++) {
        // 如果vis[i]为false，说明i是一个素数
        if (!vis[i]) {
            prime[cnt++] = i;  // 将素数i存入prime数组，并增加计数
        }
        
        // 遍历所有已找到的素数
        for (int j = 0; j < cnt; j++) {
            // 只筛选小于等于n的数
            if (i * prime[j] > n) break;  // 如果i * prime[j]大于n，停止循环
            
            vis[i * prime[j]] = 1;  // 用i的最小质因数筛去i的倍数
            
            // 如果i能被当前的素数prime[j]整除
            if (i % prime[j] == 0) break; // 结束内层循环，确保筛选的质因数是最小的
        }
    }
    
    return cnt;  // 返回素数的个数
}

int main() {
    int n;
    cin >> n;  // 输入n
    cout << euler_sieve(n) << endl;  // 输出小于等于n的素数个数
    return 0;
}

2.约数

约数的定义：约数是指能够整除一个整数的整数。换句话说，如果一个整数 a 能被另一个整数 b 整除，且没有余数，那么 b 就称为 a 的一个约数。

如果 n  mod  b  =0，则 b 是 n 的约数。

2.1试除法求约数

以下是带有详细注释的代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<int> res;

    // 遍历 1 到 n 的平方根，查找 n 的约数
    for(int i = 1; i <= n / i; i++)
    {
        if(n % i == 0)
        {
            res.push_back(i);
            if(n / i != i) // 避免重复添加
            {
                res.push_back(n / i);
            }
        }
    }

    sort(res.begin(), res.end()); // 对结果数组进行排序

    for(auto e : res)
    {
        cout << e << " "; // 输出约数
    }
    cout << endl;
}

int main()
{
    int t;
    cin >> t; // 读取测试用例的数量
    while(t--)
    {
        solve();
    }
    return 0;
}

2.2 约数的个数

#include <iostream>
#include <unordered_map>

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;        // 除以素数 i
                primes[i]++;   // 记录素数 i 的出现次数
            }
        }

        if (x > 1) primes[x]++;  // 如果 x 是素数，则记录
    }

    LL res = 1;  // 初始化结果
    // 计算约数个数
    for (auto p : primes) 
        res = res * (p.second + 1) % mod;  // 根据公式计算约数个数并取模

    cout << res << endl;  // 输出结果

    return 0;  // 程序正常结束
}

2.3约数之和

代码实现  + 详细注释

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

using namespace std;

typedef long long LL;  // 定义长整型别名

const int N = 110, mod = 1e9 + 7;  // 常量 N 和模数 mod

int main()
{
    int n;
    cin >> n;  // 读取要处理的数字的个数

    unordered_map<int, int> primes;  // 存储素因数及其对应的次数

    while (n -- )  // 对每个数字进行处理
    {
        int x;
        cin >> x;  // 读取数字 x

        // 进行素因数分解
        for (int i = 2; i <= x / i; i ++ )  // 遍历从 2 到 sqrt(x)
            while (x % i == 0)  // 如果 i 是 x 的因数
            {
                x /= i;  // 将 x 除以 i
                primes[i] ++ ;  // 记录素因数 i 的次数
            }

        // 如果 x 大于 1，说明 x 本身是一个素数
        if (x > 1) primes[x] ++ ;  // 将素数 x 也加入到 primes 中
    }

    LL res = 1;  // 初始化结果为 1
    for (auto p : primes)  // 遍历所有的素因数及其次数
    {
        LL a = p.first, b = p.second;  // a 为素因数，b 为该素因数的指数
        LL t = 1;  // 初始化每个因数的约数和为 1
        while (b -- )  // 对于每个素因数的指数
            t = (t * a + 1) % mod;  // 计算 (1 + a + a^2 + ... + a^b) 的值

        res = res * t % mod;  // 将当前素因数的约数和与结果相乘，并对 mod 取模
    }

    cout << res << endl;  // 输出最终结果

    return 0;
}

2.4.最大公约数（GCD）

整除的定义：：

1.GCD的定义：

#include<iostream>
using namespace std;
int gcd(int a , int b)
{
    return b ? gcd(b , a % b) : a;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int a , b;
        cin >> a >> b;
        cout << gcd(a , b) << endl;
    }
    return 0;
}