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

1.素数

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

1.1小素数的判定

判定一个数是否为素数，当N ≤ $10^{12}$ 时，用试除法，当n > $10^{12}$ 时，用Miller_Rabin算法

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

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

#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数组，所有项设为falsememset(prime, 0, sizeof(prime)); // 初始化prime数组// 从2开始，遍历到nfor (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;  // 输入ncout << 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;        // 除以素数 iprimes[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 和模数 modint 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 除以 iprimes[i] ++ ;  // 记录素因数 i 的次数}// 如果 x 大于 1，说明 x 本身是一个素数if (x > 1) primes[x] ++ ;  // 将素数 x 也加入到 primes 中}LL res = 1;  // 初始化结果为 1for (auto p : primes)  // 遍历所有的素因数及其次数{LL a = p.first, b = p.second;  // a 为素因数，b 为该素因数的指数LL t = 1;  // 初始化每个因数的约数和为 1while (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;
}